Problem Statement

Problems F and F2 are the same problem with different constraints on $M$. In Problem F, $1 \le M \le 4$.

You are given a positive integer $M$. Consider the following problem.

Bucket

You are given a positive integer $N$ and non-negative integer sequences $A=(A_1,A_2,\dots,A_N)$ and $B=(B_1,B_2,\dots,B_N)$ of length $N$. All elements of $A$ and $B$ are between $0$ and $M$, inclusive.

There are $N$ buckets numbered $1$ to $N$. Each bucket can hold up to $M$ liters of water. Initially, bucket $i$ contains $A_i$ liters of water.

You may perform the following operation any number of times.

• Choose two distinct buckets $i$ and $j$. Continue pouring water from bucket $i$ into bucket $j$ as long as both of the following conditions are satisfied:
• Bucket $i$ still has water remaining.
  • The amount of water in bucket $j$ is less than $M$ liters.

Your goal is to have exactly $B_i$ liters of water in bucket $i$ for all $i$. Determine whether the goal can be achieved.

You are given a non-negative integer matrix $X=(X_{i,j})(0 \le i,j \le M)$ of $(M+1)$ rows and $(M+1)$ columns. Process the following queries $Q$ times.

• You are given non-negative integers $i,j,Y$ with $0 \le i,j \le M$. Change $X_{i,j}$ to $Y$. Then, obtain non-negative integer sequences $A$ and $B$ by the following procedure.
• Initialize non-negative integer sequences $A$ and $B$ as empty sequences.
  • For $i = 0,1,\dots,M$ in this order:
• Solve Bucket for the non-negative integer sequences $A$ and $B$ of length $N = \sum_{i=0}^{M} \sum_{j=0}^{M} X_{i,j}$.

Constraints

• $1 \le M \le 4$
• $1 \le Q \le 10^6$
• $0 \le X_{i,j},Y \le 10^{17}$
• $0 \le i,j \le M$
• $\sum_{i=0}^{M} \sum_{j=0}^{M} X_{i,j} \ge 1$ at any time.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

M Q
X_{0,0}\ X_{0,1}\ \dots\ X_{0,M}
X_{1,0}\ X_{1,1}\ \dots\ X_{1,M}
\vdots
X_{M,0}\ X_{M,1}\ \dots\ X_{M,M}
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

Each query is given in the following format:

i\ j\ Y

Output

Output $Q$ lines. The $i$-th line should contain Yes if the goal can be achieved in $\mathrm{query}_i$, and No otherwise.