Problem Description

There are few pedestrians on the 4th Ring Road, and car gods often compete there.

The road is still here today, but the experienced drivers of those years are nowhere to be seen.

When Mr. B is in a bad mood, he likes to speed on the 4th Ring Road. Watching the scenery flying past the window, Mr. B thinks of Mr. R and Mr. G from the past; of YJQ and FLZ of the present; of the vastness of the universe and the infinity of space-time; and also of this problem.

Given $n, X, Y, Z$, it is guaranteed that $X$ is an integer power of $2$, $Y$ is an integer power of $3$, and $Z$ is an integer power of $5$, and that $1 \le n \le 1000$, $1 \le X \times Y \times Z \le 2000$.

You are given four arrays of length $n$: $\{a_i\}, \{b_i\}, \{c_i\}, \{r_i\}$ ($0 \le a_i, b_i, c_i, r_i \le 10^9$).

For each $(u, v, w)$, count how many solutions $\{x_i\}, \{y_i\}, \{z_i\}$ there are.

They must satisfy that for all $i$, $a_i \le x_i, b_i \le y_i, c_i \le z_i, r_i \ge x_i - a_i + y_i - b_i + z_i - c_i$.

And

$$(\sum_{i=1}^n x_i) \bmod X = u$$ $$(\sum_{i=1}^n y_i) \bmod Y = v$$ $$(\sum_{i=1}^n z_i) \bmod Z = w$$

Let the number of solutions be $F(u, v, w)$.

Output

$$\operatorname*{xor}_{0\le u< X,0\le v<Y,0\le w<Z}((uYZ+vZ+w)\times(F(u,v,w)\bmod466560001))$$

Input Format

The first line contains $n, X, Y, Z$.

The next $n$ lines each contain four integers $a_i, b_i, c_i, r_i$.

Output Format

Output one integer in one line as the answer.

3 2 3 1
0 0 0 1
0 0 0 2
0 0 0 3

573

3 2 3 5
0 0 0 1
0 0 0 2
0 0 0 3

253

Hint

Copyright Information

From THUPC (THU Programming Contest, Tsinghua University Programming Contest) 2017.

Translated by ChatGPT 5