Four Season

After extreme changes in the Earth's climate, Parsa started studying temperatures in different countries. In each country, the number of days in a year may be different.

If each season in a country lasts $k$ days, then the whole year has $4k$ days.

The temperature pattern of each country is periodic with period $4k$. In other words, the temperature of any day is the same as the temperature $4k$ days later.

Parsa observed the temperatures of $4k$ consecutive days and gives them to you. Note that he did not necessarily start collecting data from the first day of spring.

The seasons of each country are, in order:

• Spring
• Summer
• Autumn
• Winter

A summer is called hellish if the sum of temperatures in that summer is not smaller than the sum of temperatures of any other consecutive $k$ days in the year.

A winter is called freezing if the sum of temperatures in that winter is not greater than the sum of temperatures of any other consecutive $k$ days in the year.

From Parsa's point of view, a country is a four-season country if its summer is hellish and its winter is freezing.

For each test case, determine whether it is possible that the given list is a sequence of $4k$ consecutive days from such a country. Equivalently, determine whether it is possible to rotate the cyclic sequence so that:

• the year is split into spring, summer, autumn, and winter, each of length $k$
• the chosen summer is hellish
• the chosen winter is freezing

Print Yes if such a rotation exists, otherwise print No.

Input

The first line contains an integer $T$, the number of test cases.

Each test case consists of two lines:

• The first line contains an integer $k$
• The second line contains $4k$ integers $a_1, a_2, ..., a_{4k}$

Here, $a_j$ is the temperature of the $j$-th day in the given cyclic order.

Output

For each test case, print:

• Yes if the sequence can represent such a country
• No otherwise

Constraints

• $1 \le T \le 5 \times 10^4$
• $1 \le k \le 5 \times 10^4$
• $-10^9 \le a_j \le 10^9$
• the sum of $k$ over all test cases does not exceed $5 \times 10^4$.

Example 1

3
1
1 2 3 4
1
1 3 4 2
2
1 2 3 4 4 3 2 1

No
Yes
Yes