题目描述

$N$ 人の参加者と $N$ 個の問題からなるコンテストがあります。 参加者には $1$ から $N$ までの番号が付いています。 各参加者と問題の組について、その参加者がその問題を解くのにかかる時間が分かっており、 その時間は $1$ 分、$2$ 分または $3$ 分です。 $N$ 個の問題のうち、参加者 $i$ が解くのに $1$ 分かかる問題は $A_i$ 問、 $2$ 分かかる問題は $B_i$ 問、$3$ 分かかる問題は $C_i$ 問あります。

各参加者が問題を解く順番を自由に定めることで、すべての $1\ \leq\ i,\ j\ \leq\ N$ について以下が成立することがありうるか判定してください。

• 参加者 $i$ が最初の $i$ 問を解くのにかかる時間を $S$ 分、参加者 $j$ が最初の $i$ 問を解くのにかかる時間を $T$ 分とする。このとき $S\ \leq\ T$ となる。

つまり、すべての $i$ について参加者 $i$ が最初の $i$ 問を解いた時点で $1$ 位（同率でもよい）となることがありうるか判定してください。 ただし、ある問題を解いてから次の問題にうつるまでにかかる時間は無視できるものとします。

$T$ 個のテストケースが与えられるので、それぞれを解いてください。

输入格式

入力は以下の形式で標準入力から与えられる。入力の $1$ 行目は次の通りである。

$T$

そして、以下の形式で $T$ 個のテストケースが続く。

$N$ $A_1$ $B_1$ $C_1$ $:$ $A_N$ $B_N$ $C_N$

输出格式

各テストケースについて、問題文の条件が成立しうるならば Yes 、そうでなければ No と出力せよ。 $1$ 行につき $1$ 個のテストケースへの出力を行え。なお、正誤判定器は英大文字と英小文字を区別せず、どちらも受理する。

题目大意

有一场 $n$ 个参赛者、$n$ 道题的比赛。参赛者被编号为 $1$ 至 $n$。我们知道每一名参赛者解决每一道题目需要的时间，其只可能是 $1/2/3$ 分钟。在这 $n$ 道题目中，有 $A_i$ 道题目需要参赛者 $i$ 花费 $1$ 分钟解决，有 $B_i$ 道题目需要参赛者 $i$ 花费 $2$ 分钟解决，有 $C_i$ 道题目需要参赛者 $i$ 花费 $3$ 分钟解决。

假设每名参赛者都能够自由决定做题顺序，请确定如下的条件是否能够对于所有参赛者 $1\le i,j\le n$ 都成立：

• 令 $S$ 为参赛者 $i$ 完成前 $i$ 道题目的时间，$T$ 为参赛者 $j$ 完成前 $i$ 道题目的时间。条件即为 $S\le T$。

具体的说，在忽略切换题目的时间的情况下，需要确定是否对于每个参赛者 $i$，其为所有人中第一个（可能为并列）完成前 $i$ 道题目的人。

有 $T$ 组询问。

$1\le T\le 2\times 10^5,\ 1\le n \le 2\times 10^5, \ 0\le A_i,B_i,C_i\le n,\ A_i + B_i + C_i = n$。保证所有询问的 $n$ 加和 $\le 2\times 10^5$。

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

Yes
No

提示

制約

• $1\ \leq\ T\ \leq\ 2\times\ 10^5$
• $1\ \leq\ N\ \leq\ 2\times\ 10^5$
• $0\ \leq\ A_i,B_i,C_i\ \leq\ N$
• $A_i+B_i+C_i=N$
• 全テストケースにおける $N$ の総和は $2\times\ 10^5$ 以下である。

Sample Explanation 1

最初のテストケースでは、例えば以下のような場合に条件が成立します。 - 参加者 $1$ は $1$ 問目を $3$ 分、$2$ 問目を $2$ 分、$3$ 問目を $2$ 分かけて解く。 - 参加者 $2$ は $1$ 問目を $3$ 分、$2$ 問目を $2$ 分、$3$ 問目を $3$ 分かけて解く。 - 参加者 $3$ は $1$ 問目を $3$ 分、$2$ 問目を $2$ 分、$3$ 問目を $1$ 分かけて解く。