TowerPlacement

Time limit is 6 seconds.

Absurdistan is a rectangular country that is divided into a grid of R rows by C columns of unit squares. These have coordinates from (0, 0) to (R-1, C-1).

We are building broadcast towers. Each broadcast tower occupies one square of the grid. Additionally, in the future each broadcast tower will have to be anchored. The anchors for a tower must occupy either both squares that are horizontally adjacent to the tower, or both vertically-adjacent squares.

Each square can only contain at most one object (i.e., either a tower, or the anchor of exactly one tower, or nothing). Anchors of a tower cannot be placed outside the grid. This limits how towers on the boundary of Absurdistan can be anchored.

Below is an example of several correctly anchored towers, using 'T' to denote towers and different numbers to denote anchors for different towers. Note that tower with anchors denoted '5' could have also been anchored vertically.

    +----------+
    | 0       4|
    | T1  5T5 T|
    | 0T3T3   4|
    |  12T2    |
    +----------+

You are given a sequence of 50,000 not necessarily distinct squares: (qr[0], qc[0]), ..., (qr[49999], qc[49999]). These are candidates for the places of towers in Absurdistan.

The tower building committee processes these candidates in the given order, using the following algorithm:

    start with an empty set T of towers
    for each i from 0 to 49999:
        let S = (qr[i], qc[i]) be the current candidate square
        if S is already in T:
            ignore candidate number i (do nothing)
        else:
            let T' = T + {S}
            if it is possible to build and correctly anchor all towers in T':
                accept candidate number i and set T = T'
            else:
                reject candidate number i

You are given X. Return the number of the X-th (1-based index) rejected candidate, or -1 if there is no such candidate.

X is usually small. Please read the exact constraints for X carefully.

--------------------

In order to keep the input small, the sequence of candidate squares is generated pseudorandomly. Please use the following pseudocode to generate it:

state = seed
for i = 0 to 49999:
    state = (state * 1103515245 + 12345) modulo 2^31
    qr[i] = (state div 1000) mod R
    state = (state * 1103515245 + 12345) modulo 2^31
    qc[i] = (state div 1000) mod C