Problem C
Forest Fires

Fires can spread in a forest more easily if the trees in the forest are densely packed – it makes it easy for the fire to jump from tree to tree. Write a forest fire simulator which ‘grows’ a forest tree-by-tree. As the forest grows, your simulator should answer queries about whether a fire starting at tree $A$ can spread to tree $B$ (where trees $A$ and $B$ may vary with each query).

The forest is modeled as a grid of size $100 \times 100$, where each grid square can hold exactly one tree. The bottom-left grid square is $(0,0)$ and the top-right is at $(99,99)$. Each square has an associated number, with square at $(x,y)$ numbered $100 x + y$.

Fire spreads directly from tree $A$ to $B$ if $A$ is on fire and $B$ is adjacent vertically or horizontally to $A$. Fire continues to spread until has reached all the trees it can reach in the forest. Note that we are only interested in whether a fire is able to reach from tree $A$ to tree $B$, but we do not actually remove any trees related to the query.

The simulator relies on a random number generator, which is defined as:

where each simulation starts with a different ‘seed’ for $r$. Every time a random number is needed, including the first time, this generator is used to generate a new value for $r$.

Given a seed $r$ and length of simulation $n$, the simulator should proceed as follows:

1. Initialize: let $i \leftarrow 0$.

2. Stopping condition: if $i \geq n$, then stop.

3. Place a tree: choose a random square $m \leftarrow r \mod 10\, 000$ from the random number generator. If the square numbered $m$ is occupied by a tree, generate another value of $m$ in the same way. Keep doing this until $m$ is for an unoccupied square. Place a tree at square $m$, and call this tree $t_ i$.

4. Choose $A$: compute $a \leftarrow r\mod (i+1)$, and let $A \leftarrow t_ a$.

5. Choose $B$: compute $b \leftarrow r\mod (i+1)$, and let $B \leftarrow t_ b$. It is okay if $A$ and $B$ represent the same tree.

6. Fire query: discover whether a fire started at tree $A$ can burn to tree $B$.

7. Increment: let $i \leftarrow i + 1$.

8. Loop: go back to step 2.

Report a summary of the fire queries every $100$ iterations during the simulation.

Input

Input contains up to $200$ test cases. Each test case is a line containing two integer values $0 \le r < 50\, 021$, representing the seed value of the random number generator, and $0 \le n \le 10\, 000$, representing the number of times the main simulation loop should execute. Also, $n$ is a multiple of $100$. Input ends at end of file.

Output

For each test case, after each set of $100$ iterations, output the number of fire queries (step $6$ above) which succeeded. That is, the first block is between $i=0$ and $i=99$, the second block is between $i=100$ and $i=199$, etc.

4 1000
22 2000
25 1000

9 1 0 0 0 0 0 0 0 0
7 1 0 0 1 0 1 0 0 0 1 0 0 1 0 1 0 0 0 0
1 2 0 0 0 0 1 1 0 0