問題文

T 個のテストケースについて、以下の問題を解いてください。

長さ N の数列 A=(A_1,A_2,\ldots,A_N) があり、現在全ての 1\leq i\leq N について A_i=0 です。

あなたの目標は全ての 1\leq i\leq N について A_i\equiv R_i\pmod{M} が成立するようにすることです。これを実現させるため、以下の操作を任意の回数行うことができます。(一度も行わないこともできます。)

• 1\leq j\leq K を満たす整数 j を選ぶ。A の P_j 番目の要素に 1 を加える。さらに、A の Q_j 番目の要素に 1 を加える。

目標が達成可能かどうかを判定してください。

制約

• 1\leq T\leq 2\times 10^5
• 1\leq N\leq 2\times 10^5
• 2\leq M\leq 10^9
• 1\leq K\leq 2\times 10^5
• 0\leq R_i\lt M
• 1\leq P_i\leq N
• 1\leq Q_i\leq N
• 1 つの入力に含まれる N の総和、K の総和はそれぞれ 2\times 10^5 を超えない

入力例 1

3
6 3 5
0 1 0 1 2 0
1 2
1 6
4 5
5 2
5 6
6 4 7
2 3 1 2 3 0
1 4
3 2
3 5
6 5
4 6
1 2
2 4
4 5 4
2 4 2 4
1 3
1 3
2 4
2 4

出力例 1

Yes
No
Yes

1 番目のテストケースでは、次の順序で操作を行うことで目標が達成できます。

1. j=2 とする。A=(1,0,0,0,0,1) になる。
2. j=1 とする。A=(2,1,0,0,0,1) になる。
3. j=2 とする。A=(3,1,0,0,0,2) になる。
4. j=3 とする。A=(3,1,0,1,1,2) になる。
5. j=5 とする。A=(3,1,0,1,2,3) になる。

最終的に全ての 1\leq i\leq 6 について A_i\equiv R_i\pmod{3} とできていることが確認できます。