Background

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}$.

He was confused by “Truth IV” in it, so he came to you for help.

Problem Description

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:

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.

Input Format

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$.

Output Format

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

5 200
21 84 198
38 47 102
44 47 132 
63 150 166
76 79 132

4

Hint

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 T2.

Problem setter: disangan233.

Problem tester: Studying Father.

Translated by ChatGPT 5