Problem Statement

The value calculated by the following formula is called \mathrm{BMI}[\mathrm{kg}/\mathrm{m}^2]. (\div denotes division.)

• \text{Weight}[\mathrm{kg}] \div \text{Height}[\mathrm{m}] \div \text{Height}[\mathrm{m}]

In Japan, a person whose \mathrm{BMI} is 25 \; \mathrm{kg}/\mathrm{m}^2 or more is considered obese.
Determine whether a person with height H[\mathrm{cm}] and weight W[\mathrm{kg}] is considered obese in Japan.

Constraints

• 1 \leq H \leq 300
• 1 \leq W \leq 300
• All input values are integers.

Sample Input 1

180 60

Sample Output 1

No

Since the height is 180 \; \mathrm{cm}=1.8 \; \mathrm{m}, the \mathrm{BMI} is 60 \; \mathrm{kg} \div 1.8 \; \mathrm{m} \div 1.8 \; \mathrm{m}=18.5\dots \; \mathrm{kg}/\mathrm{m}^2, so this person is not considered obese.

Sample Input 2

182 188

Sample Output 2

Yes

Sample Input 3

180 81

Sample Output 3

Yes

Problem Statement

Takahashi made purchases at N stores. Initially, he had 10000 yen.
At the i-th store, he bought an item worth A_i yen and paid B_i yen. Here, A_i \leq B_i holds. If S_i = keep, he did not receive the change, and if S_i = take, he received the change.
Find the amount of money he lost compared to the case where he received the change at every store. To be precise,

• let X yen be Takahashi's final amount of money, and
• let Y yen be Takahashi's final amount of money in the case where he received the change at every store.

Find Y - X.

Constraints

• 1 \leq N \leq 100
• 1 \leq A_i \leq B_i \leq 100
• S_i is keep or take.
• N, A_i, B_i are all integers.

Sample Input 1

3
1 2 keep
3 6 take
5 9 keep

Sample Output 1

5

Takahashi's actions are as follows.

• At the first store, he bought an item worth 1 yen, paid 2 yen, and did not receive the change.
• At the second store, he bought an item worth 3 yen, paid 6 yen, and received the change.
• At the third store, he bought an item worth 5 yen, paid 9 yen, and did not receive the change.

Sample Input 2

8
36 49 take
38 73 keep
27 85 take
65 71 take
52 86 keep
48 60 keep
37 98 keep
5 38 keep

Sample Output 2

175

Problem Statement

The problem statement of Problem C is the same as Problem E. Only the constraint shown in red differ.

You are given integer sequences A=(A_1,A_2,\dots,A_N),B=(B_1,B_2,\dots,B_{N-1}) consisting of integers between 0 and M-1, inclusive. The lengths of A and B are N and N-1, respectively.
You can perform the following operation on A any number of times.

• Choose an integer i with 1 \leq i \leq N, and add 1 to A_i.

Find the minimum number of operations required to satisfy the following condition.
It can be proved that the condition can always be satisfied under the constraints of this problem.

• For i=1,2,\dots,N-1, the remainder when A_i+A_{i+1} is divided by M equals B_i.

Constraints

• 2 \leq N \leq 2 \times 10^5
• M=2
• 0 \leq A_i \leq M-1
• 0 \leq B_i \leq M-1
• All input values are integers.

Sample Input 1

3 2
1 1 1
1 1

Sample Output 1

1

If we choose i=2 for the first operation, we get A=(1,2,1).
Since A_1+A_2=1+2=3 and A_2+A_3=2+1=3, the condition is satisfied.
A=(1,1,1) does not satisfy the condition, so the answer is 1.

Sample Input 2

2 2
1 1
0

Sample Output 2

0

Sample Input 3

10 2
0 0 0 1 1 0 1 0 1 0
0 1 0 1 0 1 0 1 0

Sample Output 3

4

Problem Statement

Do there exist two circles C_1 and C_2 on the xy-plane satisfying all of the following conditions? Here, C_1 and C_2 may coincide.

• The two distinct points (P_x, P_y) and (Q_x, Q_y) lie on the circumference of C_1.
• The two distinct points (R_x, R_y) and (S_x, S_y) lie on the circumference of C_2.
• C_1 and C_2 have the same center.

You are given T test cases; solve each of them.

Constraints

• 1 \leq T \leq 5 \times 10^4
• -10^9 \leq P_x,P_y,Q_x,Q_y,R_x,R_y,S_x,S_y \leq 10^9
• (P_x, P_y) \neq (Q_x, Q_y)
• (R_x, R_y) \neq (S_x, S_y)
• All input values are integers.

Sample Input 1

3
2 0 1 1 -1 0 1 2
1 0 -1 0 0 1 0 -1
4 0 3 1 2 0 1 1

Sample Output 1

Yes
Yes
No

Consider the first test case. As shown in the figure below, if we let C_1 be the circle with center (1,0) and radius 1, and C_2 be the circle with center (1,0) and radius 2, the conditions are satisfied.

For the second test case, letting both C_1 and C_2 be the circle with center (0,0) and radius 1 satisfies the conditions.

Problem Statement

The problem statement of Problem E is the same as Problem C. Only the constraint shown in red differ.

You are given integer sequences A=(A_1,A_2,\dots,A_N) and B=(B_1,B_2,\dots,B_{N-1}) consisting of integers between 0 and M-1, inclusive. The lengths of A and B are N and N-1, respectively.
You can perform the following operation on A any number of times.

• Choose an integer i with 1 \leq i \leq N, and add 1 to A_i.

Find the minimum number of operations required to satisfy the following condition.
It can be proved that the condition can always be satisfied under the constraints of this problem.

• For i=1,2,\dots,N-1, the remainder when A_i+A_{i+1} is divided by M equals B_i.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 3 \leq M \leq 10^9
• 0 \leq A_i \leq M-1
• 0 \leq B_i \leq M-1
• All input values are integers.

Sample Input 1

3 10
4 6 7
5 5

Sample Output 1

5

If we choose i=2 for the first operation, we get A=(4,7,7).
If we choose i=1 for the second operation, we get A=(5,7,7).
If we choose i=1 for the third operation, we get A=(6,7,7).
If we choose i=2 for the fourth operation, we get A=(6,8,7).
If we choose i=1 for the fifth operation, we get A=(7,8,7).
Since A_1+A_2=7+8=15 and A_2+A_3=8+7=15, the condition is satisfied.
The condition cannot be satisfied with four or fewer operations, so the answer is 5.

Sample Input 2

2 3
1 2
2

Sample Output 2

2

Sample Input 3

10 10
0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1

Sample Output 3

40

Problem Statement

You are given length-N sequences of positive integers A=(A_1,A_2,\dots,A_N) and B=(B_1,B_2,\dots,B_N).
You are given Q queries.
Each query is of one of the following two types.

• 1 i x : Change A_i to x.
• 2 i x : Change B_i to x.

After processing each query, solve the following problem.

Takahashi needs to send an email to each of N companies and receive a reply from each of them.
Writing the email to send to the j-th company takes A_j minutes, and the reply arrives B_j minutes after it is sent.
He starts writing emails at time 0.
He can write the N emails in any order he likes, but he cannot write two or more emails simultaneously.
Find the minimum possible time at which he finishes receiving all of the replies.
Assume that the time taken to send emails is negligible.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq Q \leq 10^5
• 1 \leq A_j,B_j \leq 10^9
• In each query, 1 \leq i \leq N.
• In each query, 1 \leq x \leq 10^9.
• All input values are integers.

Sample Input 1

3 3
4 6 7
4 6 7
1 2 1
2 3 7
2 3 1

Sample Output 1

16
16
13

After processing the first query, A=(4,1,7) and B=(4,6,7).
If Takahashi starts writing the email to send to company 3 at time 0, finishes writing it at time 7, and sends it to company 3, he receives the reply at time 14.
If he starts writing the email to send to company 2 at time 7, finishes writing it at time 8, and sends it to company 2, he receives the reply at time 14.
If he starts writing the email to send to company 1 at time 8, finishes writing it at time 12, and sends it to company 1, he receives the reply at time 16.

Problem Statement

There is a length-N sequence of positive integers A=(A_1,A_2,\dots,A_N). Process the following query Q times.

• c x l r k : Update the value of A_c to x. Then, solve the following sub-problem and output the answer.

There are r-l+1 sweets. The deliciousness of the i-th sweet is A_{l+i-1}.
You decide to eat sweets until the total deliciousness of the sweets eaten becomes k or more.
What is the minimum possible number of sweets you eat, if you optimally choose which sweets to eat? Output the answer.
If the total deliciousness cannot become k or more no matter how you choose the sweets to eat, output -1 instead.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq Q \leq 10^5
• 1 \leq A_i \leq 10^9
• 1 \leq c \leq N
• 1 \leq x \leq 10^9
• 1 \leq l \leq r \leq N
• 1 \leq k \leq 10^{15}
• All input values are integers.

Sample Input 1

7 5
8 2 4 1 7 3 6
1 1 4 7 9
5 2 1 3 8
6 4 1 5 9
6 5 3 5 1
7 9 4 6 4

Sample Output 1

2
-1
4
1
1

We explain the first query.
First, update A_1 to 1. Then, A=(1,2,4,1,7,3,6). Now, solve the sub-problem.
In the sub-problem, there are four sweets, with deliciousness 1,7,3,6 in order.
To minimize the number of sweets eaten so that the total deliciousness becomes k=9 or more, it is optimal to eat the second and fourth sweets. Thus, the answer to the sub-problem is 2.

Sample Input 2

15 10
993115119 576136368 21553212 219853538 853822501 687675302 281611653 844033520 423210108 339630584 780395612 207907746 285523486 359061085 14767613
6 13801767 1 3 667406485
7 672229269 5 7 855399219
11 2367096 1 10 4016308479
6 5951398 8 8 413598120
6 196639646 5 11 2483790193
14 105322777 6 7 610670157
7 416730828 2 14 1236755516
9 838827476 5 14 4350335977
1 894919681 3 7 1132967029
6 932707551 6 15 1694677398

Sample Output 2

1
2
6
1
4
1
2
-1
2
2