P16057 [CSPro 31] Yin-Yang Dragon

The testdata on Luogu is only for community communication and is not official testdata. Official judging link: .

Below Xixiaifu Island lies a huge group of ruins, where the divine beast “Yin-Yang Dragon” lives. To obtain this treasure, Xixiaifu Ruins Exploration Co., Ltd. (hereinafter referred to as the “Company”) dispatched $p$ employees to the ruins. These employees are numbered from $1$ to $p$ in order. The ruins can be regarded as an $n \times m$ grid, with the bottom-left corner at $(1, 1)$ and the top-right corner at $(n, m)$. Initially, the position of employee $i$ is $(x_i, y_i)$. It is guaranteed that all employees’ initial positions are pairwise distinct. As a divine beast, the Yin-Yang Dragon is special. When it appears at position $\mathbf{p} = (u, v)$ with intensity $t \in [1, 7]$, it causes a transformation between yin and yang in the environment of the ruins, which in turn changes the positions of people in the ruins. Specifically, the Yin-Yang Dragon first looks in the eight directions: right, up-right, up, up-left, left, down-left, down, and down-right, and finds the nearest employee (excluding $\mathbf{p}$) in these directions, and takes that “distance”. Here, in vertical and horizontal directions, the “distance” means the length of the segment connecting the employee and the Yin-Yang Dragon; in diagonal directions, the “distance” means the length of the projection of that segment onto the horizontal axis. Imagine starting from the Yin-Yang Dragon’s position and moving in these $8$ directions simultaneously, moving $1$ unit of “distance” per unit time. If at some moment an employee is met exactly in some direction, then the traveled distance at that time is recorded as $k$; otherwise, if at some moment the boundary of the ruins is reached exactly in some direction, but no employee has been met in any direction before that, then let $k = 0$. A formal description of how to determine $k$ is as follows: Let $\mathbf{d}_0$ to $\mathbf{d}_7$ be the vectors $(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)$ in order, and let: $$ \begin{aligned} K_1 &= \{ k \in \mathbb{N}^+ \mid \exists i \in [0, 7], j \in [1, p], \text{s.t. } (x_j, y_j) = \mathbf{p} + k\mathbf{d}_i \} \\ K_2 &= \{ k \in \mathbb{N}^+ \mid \forall i \in [0, 7], (\mathbf{p} + k\mathbf{d}_i) \in [1, n] \times [1, m] \} \end{aligned} $$ where: - $(x_i, y_i)$ is the position of employee $i$ before this appearance of the Yin-Yang Dragon (this position may differ from the initial one, but for convenience we use the same notation); - $K_1$ is the set of all distances from employees to the Yin-Yang Dragon; - $K_2$ is the set of all distances from the Yin-Yang Dragon until reaching the boundary in some direction. If $K = K_1 \bigcap K_2 = \emptyset$, then let $k = 0$; otherwise let $k = \min K > 0$. For example, refer to the example in the figure below, where the bottom-left corner is $(1, 1)$, the top-right corner is $(7, 7)$, and there are $8$ employees positioned as shown. If $\mathbf{p} = (4, 4)$, then employee $1$ is exactly at the Yin-Yang Dragon’s position and is not counted; employee $3$ is not in any of the $8$ directions and is not counted; employees $2$, $4$, $5$, and $6$ have “distance” $2$ to the Yin-Yang Dragon; employees $7$, $8$, and $9$ have “distance” $3$, so $K_1 = \{2, 3\}$. Since reaching “distance” $3$ already hits the boundary of the ruins, we have $K_2 = \{1, 2, 3\}$. Therefore $k = 2$. If $\mathbf{p} = (2, 2)$, then employees $2$, $3$, $7$, $8$, and $9$ are not in any of the $8$ directions and are not counted; employees $1$ and $6$ have “distance” $2$ to the Yin-Yang Dragon; employees $4$ and $5$ have “distance” $4$, so $K_1 = \{2, 4\}$. Since at “distance” $1$ the boundary is reached in the three directions down, left, and down-left, we have $K_2 = \{1\}$. Therefore $k = 0$. :::align{center}  ::: If $k > 0$, then the employees at positions with distance $k$ in the eight directions are rotated counterclockwise around $\mathbf{p}$ by $t$ times one-eighth of a full circle. Formally: - If $k = 0$, then nothing happens. - Otherwise, $\forall i \in [0, 7]$, if there is an employee at position $\mathbf{p} + k\mathbf{d}_i$, then that employee is moved to $\mathbf{p} + k\mathbf{d}_{(i+t) \bmod 8}$. It is easy to see that after all employees finish moving, each position still contains at most one employee. For example, in the example above, take $\mathbf{p} = (4, 4), t = 1$, then the employees’ positions after the change are shown in the figure below. :::align{center}  ::: After all employees entered the ruins, the Company detected a total of $q$ appearances of the Yin-Yang Dragon. Unfortunately, due to interference from mysterious eastern forces, after these $q$ appearances, the Company lost all position information of its employees, so it hopes you can help compute the positions of all employees.

Read from standard input. The first line contains four positive integers $n, m, p, q$. The next $p$ lines each contain two positive integers $(x_i, y_i)$, representing the initial position of employee $i$. It is guaranteed that all employees’ initial positions are pairwise distinct. The next $q$ lines each contain three positive integers $u_i, v_i, t_i$, representing the position and intensity of the $i$-th appearance of the Yin-Yang Dragon detected by the Company.

Output to standard output. To reduce output size, suppose that after the $q$ appearances, the positions of all employees are $(x_1, y_1), \dots, (x_p, y_p)$. You only need to output: $$ \bigoplus_{i=1}^{p} i \times x_i + y_i $$ where $\bigoplus$ denotes bitwise XOR, i.e. the `^` operator in C/C++.

### Explanation for Sample 1 Before the Yin-Yang Dragon appears, the positions of each employee are as follows: ``` 3 6 9 2 5 8 1 4 7 ``` After the Yin-Yang Dragon appears once, the positions of each employee are as follows: ``` 6 9 8 3 5 7 2 1 4 ``` ### Constraints | Subtask ID | $n \le$ | $m \le$ | $p \le$ | $q \le$ | Points | |:----------:|:---------:|:---------:|:---------:|:---------:|:------:| | 1 | $10^3$ | $10^3$ | $10^5$ | $10^5$ | 40 | | 2 | $10^9$ | $10^9$ | $10^3$ | $10^3$ | 15 | | 3 | $10^5$ | $10^5$ | $10^5$ | $10^5$ | 25 | | 4 | $10^9$ | $10^9$ | ^ | ^ | 20 | For all testdata: $1 \le n, m \le 10^9, 1 \le p, q \le 1 \times 10^5, 1 \le x_i, u \le n, 1 \le y_i, v \le m, 1 \le t_i \le 7$. It is guaranteed that all employees’ initial positions are pairwise distinct. Translated by ChatGPT 5