B. Monster Fighting
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Busy Beaver is playing his favorite adventure game, where he battles wild monsters with monsters of his own!

In this game, there are two types of monsters: light and dark. Each monster has exactly one type, and some positive integer power level. A monster with power $$$p$$$ can defeat another monster $$$q$$$ if either $$$p \geq q$$$, or if they have the same type and $$$2p \geq q$$$.

Busy Beaver has just encountered $$$N$$$ monsters, and he also has $$$N$$$ monsters in his party. To defend against the encounter, he needs to pair his monsters with the opposing monsters such that in each pair, Busy Beaver's monster can defeat the opposing monster according to the rules above. Given the types and power levels of each of the monsters, please report whether or not such a pairing exists.

Input

Each test contains multiple test cases. The first line of input contains a single integer $$$T$$$ $$$(1 \leq T \leq 10^5)$$$, the number of test cases. The description of each test case follows.

The first line of each test case contains a single positive integer $$$N$$$ ($$$1 \leq N \leq 2 \cdot 10^5$$$).

Then, $$$N$$$ lines of input follow, describing Busy Beaver's monsters. The $$$i$$$th line contains two positive integers $$$p_i, s_i$$$ ($$$1 \leq p_i \leq 10^9, s_i \in \{0, 1\}$$$) — the power level $$$p_i$$$ and type $$$s_i$$$ of the $$$i$$$th monster. $$$s_i = 0$$$ denotes a light-type monster, and $$$s_i = 1$$$ denotes a dark-type monster.

After that, there are $$$N$$$ more lines of input, describing the encountered monsters. The $$$i$$$th line contains two positive integers $$$q_i, t_i$$$ ($$$1 \leq q_i \leq 10^9, t_i \in \{0, 1\}$$$) — the power level $$$q_i$$$ and type $$$t_i$$$ of the $$$i$$$th monster. $$$t_i = 0$$$ denotes a light-type monster, and $$$t_i = 1$$$ denotes a dark-type monster.

It is guaranteed that the sum of $$$N$$$ across all test cases is no more than $$$2 \cdot 10^5$$$.

Output

For each test case, output "YES" (without quotes) if a desired pairing exists, and "NO" (without quotes) otherwise.

You can output "YES" and "NO" in any case (for example, strings "yES", "yes" and "Yes" will be recognized as a positive response).

Scoring

There are two subtasks for this problem.

  • ($$$30$$$ points): The sum of $$$N$$$ across all test cases does not exceed $$$2 \cdot 10^3$$$.
  • ($$$70$$$ points): No additional constraints.
Example
Input
2
4
2 0
3 0
1 1
1 1
1 0
2 0
3 0
2 1
2
1 1
5 1
1 0
1000000000 0
Output
YES
NO
Note

In the sample input, there are two test cases. For the first case, we can construct a pairing as follows:

  • Your light type monster of power level $$$2$$$ can defeat the identical opposing monster.
  • Your light type monster of power level $$$3$$$ can defeat the identical opposing monster.
  • Your first dark type monster of power level $$$1$$$ can defeat the opposing dark type monster of power level $$$2$$$.
  • Your second dark type monster of power level $$$1$$$ can defeat the opposing light type monster of power level $$$1$$$.

In the second case, it can be shown that no pairing exists.