50163. Seat Assignment

I'm a slow walker, but I never walk backwards.

Task Description

We want to assign seats to Taiwan High Speed Rail (THSR). We will be given a sequence of requests for booking THSR tickets, and assign seat(s) to each request.

A THSR train consists of $n$ cars indexed from 1 to $n$.
Every car has 20 rows of seats.
Each row has two groups of seats. The first group has three seats, and the second group has two seats. We represent a seat by its car number, row number and seat number. For example, the seat at the second seat of the first row of the third car is 3 1 2.
Please refer to the following figure.

carcar

There are two kinds of requests -- single or double. A single request will get one seat. A double request will get two seats next to each other (if available). If that is not available, the double request will be split into two single request. All seats are available in all cars at the beginning.
We will look for available seats in a car-by-car, row-by-row, and seat-by-seat manner. That is. we try the first car before the second car, the first row before the second row, and the first seat before the second seat.

The following figure shows how we assign seats to 6 requests -- 2, 1, 1, 2, 2 and 1.

samplesample

Input Format

The first line contains the number of cars in the train, $n$.
The second line contains a sequence $R$ of requests, which is either 1 or 2.
You should process the whole sequence until EOF. It is guaranteed that there will be enough seats for all requests.

  • $1 \leq n \leq 1000$

Output Format

We output one line for each request.
For a single request we output its car number, row number and seat number separated by a space. For a double request we output the two seats in a single line, with the same format as the single request.

Subtask

  • 20 points: There are less than 100 requests.
  • 80 points: There are at least 50000 requests.

Hint

  • We should memorize the seat assigned to the last single request to help us find the next single seat faster. We can also do the same for the double request.

Sample Input 1

1
2 1 1 2 2 1

Sample Output 1

1 1 1 1 1 2
1 1 3
1 1 4
1 2 1 1 2 2
1 2 4 1 2 5
1 1 5

Discussion