| Author: | A. Klenin, G. Grenkin | Time limit: | 1 sec | |
| Input file: | input.txt | Memory limit: | 256 Mb | |
| Output file: | output.txt |
Vladivostok Hackathon was an event where several student teams were invited to invent and prototype their fresh and useful software ideas in several days.
Young programmer Vasya and his team suggested original and exciting game: Tetris. Game implementation turned to be more complex than young programmers expected, so they simplified the rules.
A game is played on a rectangular field of H rows and W columns of cells. Each cell is either occupied or free. A piece takes a single cell. New piece appears at some cell on the top row, and starts to fall down in steps. On every step a player can choose any free cell of the three cells in a row below the piece — directly under it, a single cell to the right or a single cell to the left.
A piece stops dropping when it either reaches the bottom row, or the row below it is occupied and the player did not choose to move the piece right or left. After the piece stops, next piece immediately appears. Nothing else happens in the game — no rows disappearing, no score, etc.
While Vasya's team was presenting the game to the jury, it crashed and refused to start again. The only proof that the game ever worked is the log file which it wrote on the previous run. Log file contains data about N pieces — the column where the piece appeared and the column where it stopped.
Your program must, given field a description and a game log, determine whether the log could be the result of a correct game, and, if not, what is the first piece which could not fall as described in the log.
In the sample 2, after first 6 pieces fall and 7th one appears, the field looks as follows:
.#.... ..#... ..#... ..#... .##..#It is impossible to move the piece to the 6th column, so the log in incorrect.
Input file contains integers W H N, followed by N pairs of integers x1 x2 — initial and final column of each piece.
Output file must contain a single integer — the number of first incorrectly positioned piece, or 0 if all pieces are positioned correctly.
1 ≤ W, H ≤ 104, 1 ≤ N ≤ 106, 1 ≤ x1, x2 ≤ W
| No. | Input file (input.txt) |
Output file (output.txt) |
|---|---|---|
| 1 | |
|
| 2 | |
|