P9031 [COCI 2022/2023 #1] Iksevi

After writing code for ten years, Vinko decided to change careers and become a potter. On his first day at the new job, he was given a difficult task.

Vinko needs to cover the floor of a concert hall using square tiles. He will not align the tile edges parallel to the walls; instead, he chooses to align the diagonals of the tiles parallel to the walls. Vinko has not yet decided the tile size, but he knows that all tiles must be the same size, and the diagonal length must be a positive even integer. The first tile Vinko places will have a corner touching the left wall and the back wall. After that, each tile he places shares at least one full edge with at least one tile that has already been placed. He will repeat this process until the entire $10^7 \times 10^7$ square millimeter floor is covered. Besides being a programmer and a potter, Vinko is also an excellent musician. Because of that, he knows there are $n$ points on the floor that are crucial for the hall’s acoustics. If a tile corner lies on one of these $n$ points, the acoustics of the hall will improve significantly.  As shown in the figure, the left diagram is a tiling with diagonal length $4$. Under this tiling, the point $(2,4)$ lies on a tile corner, so it satisfies the condition and greatly improves the acoustics, but the points $(4,3)$ and $(5,1)$ do not. The right diagram is a tiling with diagonal length $2$. In this tiling, the point $(4,3)$ lies on the corners of four tiles, while $(2,4)$ and $(5,1)$ do not. Help Vinko determine, for each of the $n$ points, how many tile sizes can make the $i$-th point lie on a tile corner after the floor is fully covered.

The first line contains an integer $n$, the number of acoustically important points. The next $n$ lines each contain two integers $x_i,y_i$, representing the distances from the $i$-th acoustically important point to the left wall and the back wall.

Output $n$ lines, each containing one integer. Line $i$ should contain the number of tile sizes that can make the $i$-th acoustically important point lie on a tile corner.

| Subtask | Score | Constraints | | :-----------: | :-----------: | :-----------: | | $1$ | $15$ | $1\leq n \leq 10^4,0\leq x_i,y_i \leq 100$ | | $2$ | $55$ | $1\leq n \leq 10^4,0\leq x_i,y_i \leq 10^7$ | | $3$ | $40$ | $1\leq n \leq 10^6,0\leq x_i,y_i \leq 10^7$ | This problem is worth $110$ points in total. Translated by ChatGPT 5