P5614 [MtOI2019] Mo Siyuan

You are strong if you are strong, but $\mathsf S\mathsf{\color{red} iyuan}$ is stronger than you. ——$\mathsf S \mathsf{\color{red} iyuan}$. Recently, disangan233 found a game for OIers: [Mo $\color{black} \mathsf S \mathsf{\color{red} iyuan}$](https://lmoliver.github.io/mosiyuan/index.html). He was confused by “Truth IV” in it, so he came to you for help.

You are given $1$ positive integer $M$ and $n$ $(n\leq 5)$ positive-integer triples $\{a_i,b_i,c_i\}$ $(a_i,b_i,c_i\leq M\leq 2000)$. Please find the number of all **ordered** positive-integer triples $\{x,y,z\}$ $(x,y,z \leq M)$ that satisfy: $$ \forall i\leq n ,s.t.~|a_i-x|\oplus |b_i-y|\oplus |c_i-z| = 9 $$ Here, $\forall$ means “for all”, $s.t.$ means “such that”, and $A \oplus B \oplus C$ is the XOR of $A,B,C$. In C++, `A^B^C` or `A xor B xor C` is exactly the value of $A \oplus B \oplus C$. A template is provided here: ```cpp if ((a ^ b ^ c) == 9) { Your code here... } ``` For two ordered triples $A,B$, if $x_A \not =x_B$ or $y_A \not =y_B$ or $z_A \not =z_B$, then $A$ and $B$ are considered different.

There are $n+1$ lines in total. The first line contains $2$ positive integers $n$ and $M$. In the next $n$ lines, the $i$-th line contains $3$ positive integers $a_i,b_i,c_i$.

There is $1$ line in total. Output $1$ non-negative integer, which is the required answer.

#### Sample Explanation 1 All $\{x,y,z\}$ that satisfy the conditions are: $\{88,88,120\}$, $\{88,104,104\}$, $\{120,120,120\}$, and $\{120,136,104\}$. There are $4$ in total. ### Subtasks For $10\%$ of the data, it is guaranteed to be exactly the same as the sample. For $60\%$ of the data, it is guaranteed that $M\leq 200$. For all data, it is guaranteed that $a_i,b_i,c_i\leq M\leq 2000$ and $n\leq 5$. ### Source [MtOI2019 Extra Round](https://www.luogu.org/contest/22614) T2. Problem setter: disangan233. Problem tester: Studying Father. Translated by ChatGPT 5