Problem Statement

We have a grid with H horizontal rows and W vertical columns, where each square contains an integer. The integer written on the square at the i-th row from the top and j-th column from the left is A_{i, j}.

Determine whether the grid satisfies the condition below.

A_{i_1, j_1} + A_{i_2, j_2} \leq A_{i_2, j_1} + A_{i_1, j_2} holds for every quadruple of integers (i_1, i_2, j_1, j_2) such that 1 \leq i_1 < i_2 \leq H and 1 \leq j_1 < j_2 \leq W.

Constraints

• 2 \leq H, W \leq 50
• 1 \leq A_{i, j} \leq 10^9
• All values in input are integers.

Sample Input 1

3 3
2 1 4
3 1 3
6 4 1

Sample Output 1

Yes

There are nine quadruples of integers (i_1, i_2, j_1, j_2) such that 1 \leq i_1 < i_2 \leq H and 1 \leq j_1 < j_2 \leq W. For all of them, A_{i_1, j_1} + A_{i_2, j_2} \leq A_{i_2, j_1} + A_{i_1, j_2} holds. Some examples follow.

• For (i_1, i_2, j_1, j_2) = (1, 2, 1, 2), we have A_{i_1, j_1} + A_{i_2, j_2} = 2 + 1 \leq 3 + 1 = A_{i_2, j_1} + A_{i_1, j_2}.
• For (i_1, i_2, j_1, j_2) = (1, 2, 1, 3), we have A_{i_1, j_1} + A_{i_2, j_2} = 2 + 3 \leq 3 + 4 = A_{i_2, j_1} + A_{i_1, j_2}.
• For (i_1, i_2, j_1, j_2) = (1, 2, 2, 3), we have A_{i_1, j_1} + A_{i_2, j_2} = 1 + 3 \leq 1 + 4 = A_{i_2, j_1} + A_{i_1, j_2}.
• For (i_1, i_2, j_1, j_2) = (1, 3, 1, 2), we have A_{i_1, j_1} + A_{i_2, j_2} = 2 + 4 \leq 6 + 1 = A_{i_2, j_1} + A_{i_1, j_2}.
• For (i_1, i_2, j_1, j_2) = (1, 3, 1, 3), we have A_{i_1, j_1} + A_{i_2, j_2} = 2 + 1 \leq 6 + 4 = A_{i_2, j_1} + A_{i_1, j_2}.

We can also see that the property holds for the other quadruples: (i_1, i_2, j_1, j_2) = (1, 3, 2, 3), (2, 3, 1, 2), (2, 3, 1, 3), (2, 3, 2, 3).
Thus, we should print Yes.

Sample Input 2

2 4
4 3 2 1
5 6 7 8

Sample Output 2

No

We should print No because the condition is not satisfied.
This is because, for example, we have A_{i_1, j_1} + A_{i_2, j_2} = 4 + 8 > 5 + 1 = A_{i_2, j_1} + A_{i_1, j_2} for (i_1, i_2, j_1, j_2) = (1, 2, 1, 4).

Problem Statement

You are given a string S consisting of lowercase and uppercase English letters. The length of S is odd.
If the number of uppercase letters in S is greater than the number of lowercase letters, convert all lowercase letters in S to uppercase.
Otherwise, convert all uppercase letters in S to lowercase.

Constraints

• S is a string consisting of lowercase and uppercase English letters.
• The length of S is an odd number between 1 and 99, inclusive.

Sample Input 1

AtCoder

Sample Output 1

atcoder

The string AtCoder contains five lowercase letters and two uppercase letters. Thus, convert all uppercase letters in AtCoder to lowercase, which results in atcoder.

Sample Input 2

SunTORY

Sample Output 2

SUNTORY

The string SunTORY contains two lowercase letters and five uppercase letters. Thus, convert all lowercase letters in SunTORY to uppercase, which results in SUNTORY.

Sample Input 3

a

Sample Output 3

a

Problem Statement

There are N dominoes numbered from 1 to N. The size of domino i is S_i.
Consider arranging some dominoes in a line from left to right and then toppling them. When domino i falls to the right, if the size of the domino placed immediately to the right of domino i is at most 2 S_i, then that domino also falls to the right.

You decided to choose two or more dominoes and arrange them in a line from left to right. The arrangement of dominoes must satisfy the following conditions:

• The leftmost domino is domino 1.
• The rightmost domino is domino N.
• When only domino 1 is toppled to the right, domino N eventually falls to the right as well.

Does an arrangement of dominoes satisfying the conditions exist? If it exists, what is the minimum number of dominoes that need to be arranged?

You are given T test cases, solve the problem for each of them.

Constraints

• 1 \leq T \leq 10^5
• 2 \leq N \leq 2 \times 10^5
• 1 \leq S_i \leq 10^9
• The sum of N over all test cases is at most 2 \times 10^5.
• All input values are integers.

Sample Input 1

3
4
1 3 2 5
2
1 100
10
298077099 766294630 440423914 59187620 725560241 585990757 965580536 623321126 550925214 917827435

Sample Output 1

4
-1
3

For the 1st test case, arranging the dominoes from left to right in the order domino 1, domino 3, domino 2, domino 4 satisfies the conditions in the problem statement. Specifically, for the 3rd condition, when only domino 1 is toppled to the right, the dominoes fall in the following order:

• Domino 3 is placed to the right of domino 1. Since the size of domino 3, S_3 = 2, is not greater than S_1 \times 2 = 1 \times 2 = 2, domino 3 also falls to the right.
• Domino 2 is placed to the right of domino 3. Since the size of domino 2, S_2 = 3, is not greater than S_3 \times 2 = 2 \times 2 = 4, domino 2 also falls to the right.
• Domino 4 is placed to the right of domino 2. Since the size of domino 4, S_4 = 5, is not greater than S_2 \times 2 = 3 \times 2 = 6, domino 4 also falls to the right.

It is impossible to achieve the conditions in the problem statement by arranging 3 or fewer dominoes, so the answer is 4.

Problem Statement

Snuke the doctor prescribed N kinds of medicine for Takahashi. For the next a_i days (including the day of the prescription), he has to take b_i pills of the i-th medicine. He does not have to take any other medicine.

Let the day of the prescription be day 1. On or after day 1, when is the first day on which he has to take K pills or less?

Constraints

• 1 \leq N \leq 3 \times 10^5
• 0 \leq K \leq 10^9
• 1 \leq a_i,b_i \leq 10^9
• All input values are integers.

Sample Input 1

4 8
6 3
2 5
1 9
4 2

Sample Output 1

3

On day 1, he has to take 3,5,9, and 2 pills of the 1-st, 2-nd, 3-rd, and 4-th medicine, respectively. In total, he has to take 19 pills on this day, which is not K(=8) pills or less.
On day 2, he has to take 3,5, and 2 pills of the 1-st, 2-nd, and 4-th medicine, respectively. In total, he has to take 10 pills on this day, which is not K(=8) pills or less.
On day 3, he has to take 3 and 2 pills of the 1-st and 4-th medicine, respectively. In total, he has to take 5 pills on this day, which is K(=8) pills or less for the first time.

Thus, the answer is 3.

Sample Input 2

4 100
6 3
2 5
1 9
4 2

Sample Output 2

1

Sample Input 3

15 158260522
877914575 2436426
24979445 61648772
623690081 33933447
476190629 62703497
211047202 71407775
628894325 31963982
822804784 50968417
430302156 82631932
161735902 80895728
923078537 7723857
189330739 10286918
802329211 4539679
303238506 17063340
492686568 73361868
125660016 50287940

Sample Output 3

492686569

Problem Statement

There is a printing machine that prints line segments on the xy-plane by emitting a laser.

• At the start of printing, the laser position is at coordinate (0, 0).

• When printing a line segment, the procedure below is followed.

  • First, move the laser position to one of the endpoints of the line segment.
    • One may start drawing from either endpoint.
  • Then, move the laser position in a straight line from the current endpoint to the other endpoint while emitting the laser.
    • It is not allowed to stop printing in the middle of a line segment.

• When not emitting the laser, the laser position can move in any direction at a speed of S units per second.

• When emitting the laser, the laser position can move along the line segment being printed at a speed of T units per second.
• The time required for operations other than moving the laser position can be ignored.

Takahashi wants to print N line segments using this printing machine.
The i-th line segment connects coordinates (A_i, B_i) and (C_i, D_i).
Some line segments may overlap, in which case he needs to print the overlapping parts for each line segment separately.

What is the minimum number of seconds required to complete printing all the line segments when he operates the printing machine optimally?

Constraints

• All input values are integers.
• 1 \le N \le 6
• 1 \le T \le S \le 1000
• -1000 \le A_i,B_i,C_i,D_i \le 1000
• (A_i,B_i) \neq (C_i,D_i) ( 1 \le i \le N )

Sample Input 1

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

Sample Output 1

6.44317475868633722080

• Emit the laser while moving the laser position from (0,0) to (0,2), printing the second line segment.
  • This takes 2 seconds.
• Move the laser position from (0,2) to (1,3) without emitting the laser.
  • This takes \sqrt{2}/2 seconds.
• Emit the laser while moving the laser position from (1,3) to (2,1), printing the first line segment.
  • This takes \sqrt{5} seconds.
• Move the laser position from (2,1) to (2,0) without emitting the laser.
  • This takes 1/2 second.
• Emit the laser while moving the laser position from (2,0) to (3,0), printing the third line segment.
  • This takes 1 second.
• The total time taken is 2 + (\sqrt{2}/2) + \sqrt{5} + (1/2) + 1 \approx 6.443175 seconds.

Sample Input 2

2 1 1
0 0 10 10
0 2 2 0

Sample Output 2

20.97056274847714058517

Sample Input 3

6 3 2
-1000 -1000 1000 1000
1000 -1000 -1000 1000
-1000 -1000 1000 1000
1000 -1000 -1000 1000
1000 1000 -1000 -1000
-1000 1000 1000 -1000

Sample Output 3

9623.35256169626864153344

Multiple line segments overlap here, and you need to print the overlapping parts for each line segment separately.

Sample Input 4

6 10 8
1000 1000 -1000 -1000
1000 -1000 -1000 -1000
-1000 1000 1000 1000
-1000 1000 -1000 -1000
1000 1000 1000 -1000
1000 -1000 -1000 1000

Sample Output 4

2048.52813742385702910909