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

Input

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

Output

No
Yes
Yes