Problem Statement

The versions of a certain OS in chronological order are "Ocelot", "Serval", "Lynx".
Determine whether version X is the same as or newer than version Y.

Constraints

• Each of X and Y is one of "Ocelot", "Serval", "Lynx" (without quotation marks).

Sample Input 1

Serval Ocelot

Sample Output 1

Yes

Version Serval is the same as or newer than version Ocelot. Therefore, print Yes.

Sample Input 2

Serval Lynx

Sample Output 2

No

Version Serval is not the same as nor newer than version Lynx. Therefore, print No.

Sample Input 3

Ocelot Ocelot

Sample Output 3

Yes

Version Ocelot itself is the same as or newer than version Ocelot. Therefore, print Yes.

Problem Statement

You are given a string S of length at least 3 consisting of lowercase English letters.
S contains exactly two types of characters, and exactly one character is different from the others. Find that one character.

For example, if S is odd, report o.

Constraints

• S is a string of length at least 3 and at most 10 consisting of lowercase English letters.
• S contains exactly two types of characters, and exactly one character is different from the others.

Sample Input 1

odd

Sample Output 1

o

In odd, the character different from the others is o.

Sample Input 2

dad

Sample Output 2

a

In dad, the character different from the others is a.

Sample Input 3

wwwwwwwwwv

Sample Output 3

v

In wwwwwwwwwv, the character different from the others is v.

Problem Statement

There are N versions of a certain OS, numbered 1,2,\dots,N in chronological order.
There are N PCs, and initially the OS version of the i-th PC is i.

Perform Q operations in order. The i-th operation is as follows:

• Upgrade all PCs whose current OS version is X_i or earlier to version Y_i(>X_i). Then, print the number of PCs upgraded in this operation.

Note that for i<Q, the upgrades from the i-th operation are performed before proceeding to the (i+1)-th operation.

Constraints

• All input values are integers.
• 2 \le N \le 10^6
• 1 \le Q \le 2 \times 10^5
• 1 \le X_i < Y_i \le N

Sample Input 1

8 5
2 6
3 5
1 7
5 7
7 8

Sample Output 1

2
1
0
3
7

This input contains five operations.

• Initially, the versions of the eight PCs are 1,2,3,4,5,6,7,8.
• In the first operation, PCs with version 2 or earlier are upgraded to version 6.
  • This operation upgrades two PCs, and the versions of the PCs become 6,6,3,4,5,6,7,8.
• In the second operation, PCs with version 3 or earlier are upgraded to version 5.
  • This operation upgrades one PC, and the versions of the PCs become 6,6,5,4,5,6,7,8.
• In the third operation, PCs with version 1 or earlier are upgraded to version 7.
  • This operation upgrades zero PCs, and the versions of the PCs become 6,6,5,4,5,6,7,8.
• In the fourth operation, PCs with version 5 or earlier are upgraded to version 7.
  • This operation upgrades three PCs, and the versions of the PCs become 6,6,7,7,7,6,7,8.
• In the fifth operation, PCs with version 7 or earlier are upgraded to version 8.
  • This operation upgrades seven PCs, and the versions of the PCs become 8,8,8,8,8,8,8,8.

Problem Statement

You are given a string S of length N consisting of 0 and 1.

You can perform the following operation on S any number of times (possibly zero):

• Delete the first or last character, flip it (change 0 to 1 or 1 to 0), and insert it back at any position. More formally, let r(0)= 1 and r(1)= 0, and perform one of the following: (Here, S_i denotes the i-th character of S.)
  • Choose any i\ (1\leq i\leq N) and change S to S_2\dots S_i\,r(S_1)\,S_{i+1}\dots S_N.
  • Choose any i\ (0\leq i\leq N-1) and change S to S_1\dots S_i\,r(S_N)\,S_{i+1}\dots S_{N-1}.

Find the minimum number of operations required to make all characters of S the same. It can be proved that such a sequence of operations always exists.

You are given T test cases, so solve each of them.

Constraints

• 1\leq T\leq 2\times 10^5
• 2\leq N \leq 5\times 10^5
• T and N are integers.
• S is a string of length N consisting of 0 and 1.
• The sum of N over all test cases is at most 5\times 10^5.

Sample Input 1

3
5
01001
3
000
15
110010111100101

Sample Output 1

4
0
16

For the first test case, for example, you can make all characters of S into 0 with four operations as follows. It is impossible to make all characters of S the same with three or fewer operations, so the answer is 4.

• Delete the first character 0, and insert 1 between the 1st and 2nd characters (in S after deletion). S becomes 11001.
• Delete the first character 1, and insert 0 between the 2nd and 3rd characters (in S after deletion). S becomes 10001.
• Delete the last character 1, and insert 0 at the end (in S after deletion). S becomes 10000.
• Delete the first character 1, and insert 0 at the beginning (in S after deletion). S becomes 00000.

For the second test case, all characters of S are the same from the beginning, so no operation is needed.

Problem Statement

Takahashi and Aoki walk on a two-dimensional plane.

Takahashi's start point is (TS_X, TS_Y) and goal point is (TG_X, TG_Y). Aoki's start point is (AS_X, AS_Y) and goal point is (AG_X, AG_Y).

They simultaneously depart from their respective start points and walk straight toward their respective goal points at speed 1, and stop when they reach their respective goal points. (Note that they depart simultaneously, but they do not necessarily stop at the same time.)

Find the distance between them at the moment when the distance between them is shortest (including the moment they depart and after they stop).

Here, distance refers to Euclidean distance. That is, the distance between two points (x_1,y_1),(x_2,y_2) is defined as \sqrt{(x_1-x_2)^2+(y_1-y_2)^2}.

You are given T test cases, so solve each of them.

Constraints

• 1\leq T\leq 2\times 10^5
• -100\leq TS_X,TS_Y,TG_X,TG_Y,AS_X,AS_Y,AG_X,AG_Y \leq 100
• (TS_X,TS_Y)\neq (TG_X,TG_Y)
• (AS_X,AS_Y)\neq (AG_X,AG_Y)
• All input values are integers.

Sample Input 1

4
0 0 -2 2
-1 -1 4 4
4 0 2 0
6 0 8 0
1 0 1 1
-1 0 1 1
-8 9 2 6
-10 -10 17 20

Sample Output 1

1.000000000000000
2.000000000000000
0.000000000000000
1.783905950993199

For the first test case, let time 0 be the moment they depart. Their behavior is as follows:

• Time 0: Takahashi departs from (0,0) and starts walking toward (-2,2) at speed 1. At the same time, Aoki departs from (-1,-1) and starts walking toward (4,4) at speed 1.
• Time 2\sqrt{2}: Takahashi reaches his goal point (-2,2) and stops. At this time, Aoki is at (1,1) and is still walking.
• Time 5\sqrt{2}: Aoki reaches his goal point (4,4) and stops.

The distance between them is shortest at time \frac{1}{\sqrt{2}}, when Takahashi and Aoki are at (-\frac{1}{2},\frac{1}{2}) and (-\frac{1}{2},-\frac{1}{2}) respectively, and the distance is 1.

For the second test case, the distance between them is shortest at the moment they depart, and the distance at that time is 2.

For the third test case, the distance between them is shortest after they both stop, and the distance at that time is 0.

Problem Statement

AtCoder Inc.'s online shop currently handles N products, and the stock of product i is A_i units remaining.

Process the following Q orders in order. The i-th order is as follows:

• Buy k_i units each of products l_i,l_i+1,\dots,r_i. For products with fewer than k_i units, buy all available units. Report the total number of products bought in this order.

Note that for i<Q, the stock of products bought in the i-th order is reduced before proceeding to the (i+1)-th order.

Constraints

• All input values are integers.
• 1 \le N \le 3 \times 10^5
• 1 \le A_i \le 10^{15}
• 1 \le Q \le 3 \times 10^5
• 1 \le l_i \le r_i \le N
• 1 \le k_i \le 10^9

Sample Input 1

6
2 6 4 5 7 5
5
1 6 1
3 5 4
4 4 1
2 5 1
1 6 100

Sample Output 1

6
11
0
2
10

This input contains 5 orders.

• Initially, the stocks of the products are (from product 1 onward) 2,6,4,5,7,5 units.
• The first order is l_1 = 1, r_1 = 6, k_1 = 1.
  • In this order, 1,1,1,1,1,1 units of the products are bought, for a total of 6 units.
  • After this, the stocks of the products become 1,5,3,4,6,4 units.
• The second order is l_2 = 3, r_2 = 5, k_2 = 4.
  • In this order, 0,0,3,4,4,0 units of the products are bought, for a total of 11 units.
  • After this, the stocks of the products become 1,5,0,0,2,4 units.
• The third order is l_3 = 4, r_3 = 4, k_3 = 1.
  • In this order, 0,0,0,0,0,0 units of the products are bought, for a total of 0 units.
  • After this, the stocks of the products become 1,5,0,0,2,4 units.
• The fourth order is l_4 = 2, r_4 = 5, k_4 = 1.
  • In this order, 0,1,0,0,1,0 units of the products are bought, for a total of 2 units.
  • After this, the stocks of the products become 1,4,0,0,1,4 units.
• The fifth order is l_5 = 1, r_5 = 6, k_5 = 100.
  • In this order, 1,4,0,0,1,4 units of the products are bought, for a total of 10 units.
  • After this, the stocks of the products become 0,0,0,0,0,0 units.

Problem Statement

There are N items numbered from 1 to N. The weight of item i is W_i and the value is V_i.

You are given Q queries, so process them in order. The j-th query is as follows:

• Integers L_j, R_j, C_j\ (1\leq L_j\leq R_j\leq N) are given. When choosing some (possibly zero) items from items L_j,L_j+1,\dots,R_j such that the total weight does not exceed C_j, find the maximum possible total value of the chosen items.

Constraints

• 1\leq N \leq 2\times 10^4
• 1\leq Q \leq 2\times 10^5
• 1\leq W_i \leq 500
• 1\leq V_i \leq 10^9
• 1\leq L_j \leq R_j \leq N
• 1\leq C_j \leq 500
• All input values are integers.

Sample Input 1

4
3 4
5 8
1 2
2 3
3
1 4 7
2 4 10
1 2 2

Sample Output 1

11
13
0

For the first query, among items 1,2,3,4, if you choose items 2,4, the total weight is 5+2=7, which does not exceed C_1=7, and the total value is 8+3=11. This is the maximum.

For the second query, even if you choose all items 2,3,4, the total weight is 5+1+2=8, which does not exceed C_2=10, and you can achieve a total value of 8+2+3=13.

For the third query, both items 1,2 have weights exceeding C_3=2, so you cannot choose any item, and the maximum total value is 0.

Sample Input 2

8
167 430302156
22 623690081
197 476190629
176 24979445
22 877914575
247 211047202
232 822804784
25 628894325
8
6 8 176
3 5 80
1 7 310
4 8 368
4 5 218
3 4 431
4 6 228
1 1 239

Sample Output 2

628894325
877914575
2324409440
2329613684
902894020
501170074
902894020
430302156