{"problem":{"name":"Everyone is a winner","description":{"content":"We have a contest with $N$ participants and $N$ problems. The participants are numbered $1$ through $N$. For each pair of a participant and a problem, we know the time it takes for the participant to ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc053_d"},"statements":[{"statement_type":"Markdown","content":"We have a contest with $N$ participants and $N$ problems. The participants are numbered $1$ through $N$. For each pair of a participant and a problem, we know the time it takes for the participant to solve the problem, and it is $1$, $2$, or $3$ minutes. Among the $N$ problems, there are $A_i$ problems that Participant $i$ takes $1$ minute to solve, $B_i$ problems that s/he takes $2$ minutes to solve, and $C_i$ problems that s/he takes $3$ minutes to solve.\nDetermine whether it is possible for the following to hold for every $1 \\leq i, j \\leq N$ when the participants can freely decide the order they solve the problems.\n\n*   Let $S$ be the total time Participant $i$ takes to solve the first $i$ problems, and $T$ be the total time Participant $j$ takes to solve the first $i$ problems. Then, we have $S \\leq T$.\n\nIn other words, determine whether it is possible that Participant $i$ places first (possibly with ties) when they have solved the first $i$ problems, ignoring the time it takes for them to switch between problems.\nGiven $T$ test cases, solve each of them.\n\n## Constraints\n\n*   $1 \\leq T \\leq 2\\times 10^5$\n*   $1 \\leq N \\leq 2\\times 10^5$\n*   $0 \\leq A_i,B_i,C_i \\leq N$\n*   $A_i+B_i+C_i=N$\n*   The sum of $N$ over all test cases is at most $2\\times 10^5$.\n\n## Input\n\nInput is given from Standard Input in the following format. The first line is as follows:\n\n$T$\n\nThen, $T$ test cases follow, each in the format below:\n\n$N$\n$A_1$ $B_1$ $C_1$\n$:$\n$A_N$ $B_N$ $C_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc053_d","tags":[],"sample_group":[["2\n3\n0 2 1\n0 1 2\n1 1 1\n3\n0 2 1\n0 0 3\n1 1 1","Yes\nNo\n\nIn the first test case, one scenario that satisfies the condition is as follows:\n\n*   Participant $1$ solves the first problem in $3$ minutes, the second in $2$ minutes, and the third in $2$ minutes;\n*   Participant $2$ solves the first problem in $3$ minutes, the second in $2$ minutes, and the third in $3$ minutes;\n*   Participant $3$ solves the first problem in $3$ minutes, the second in $2$ minutes, and the third in $1$ minutes."]],"created_at":"2026-03-03 11:01:14"}}