The Fourth Ring Road is sparsely populated, where racing legends often compete.

Today the lanes remain as they were, but the veteran drivers of the past are nowhere to be seen.

When B-jun is in a bad mood, he likes to race on the Fourth Ring Road. Watching the scenery fly by outside the window, B-jun thinks of R-jun and G-jun from the past; thinks of YJQ and FLZ of the present; thinks of the vastness of the universe and the infinity of space-time; and also thinks 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$, $Z$ is an integer power of $5$, and $1 \leq n \leq 1000, 1 \leq XYZ \leq 2000$.

Input four arrays of length $n$: $\{a_i\}, \{b_i\}, \{c_i\}, \{r_i\}$ ($0 \leq a_i, b_i, c_i, r_i \leq 1000000000$).

For each $(u, v, w)$, find the number of solutions $\{x_i\}, \{y_i\}, \{z_i\}$ such 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:

$$\left(\sum_{i=1}^{n} x_i \right)\bmod X = u$$

$$\left( \sum_{i=1}^{n} y_i \right) \bmod Y = v$$

$$\left(\sum_{i=1}^{n} z_i \right)\bmod Z = w$$

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

Output:

$$\mathop{\mathrm{xor}} \limits_{\substack{0 \leq u < X \\ 0 \leq v < Y \\ 0 \leq w < Z}} ((u \cdot Y \cdot Z + v \cdot Z + w) \times (F(u, v, w) \bmod 466560001))$$

Input

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

A single integer representing the answer.

Examples

Input 1

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

Output 1

573

Input 2

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

Output 2

253