Problem Statement

You are given a string S consisting of lowercase English letters.

Output the string T determined as follows.

• If the last character of S is e, T is the string obtained by appending r to the end of S.
• If the last character of S is not e, T is the string obtained by appending er to the end of S.

Constraints

• S is a string consisting of lowercase English letters.
• The length of S is between 1 and 10, inclusive.

Sample Input 1

live

Sample Output 1

liver

The last character of live is e, so the string liver, obtained by appending r to the end of live, is the string T to be outputted.

Sample Input 2

femur

Sample Output 2

femurer

The last character of femur is not e, so the string femurer, obtained by appending er to the end of femur, is the string T to be outputted.

Sample Input 3

chimpanzee

Sample Output 3

chimpanzeer

The last character of chimpanzee is e, so the string chimpanzeer, obtained by appending r to the end of chimpanzee, is the string T to be outputted.

Problem Statement

S is a string of length N consisting of lowercase English letters.
T is a string of length N consisting of lowercase English letters and *.
We say that S matches T if and only if T can be made equal to S by replacing each * in T with some lowercase English letter.
Determine whether S matches T.

Constraints

• 1 \leq N \leq 100
• S is a string of length N consisting of lowercase English letters.
• T is a string of length N consisting of lowercase English letters and *.

Sample Input 1

8
chokudai
**o*u*ai

Sample Output 1

Yes

By replacing the first, second, fourth, and sixth characters of T, which are *, with c, h, k, and d, respectively, T can be made equal to S.

Sample Input 2

5
snuke
snake

Sample Output 2

No

Sample Input 3

5
yiwiy
*****

Sample Output 3

Yes

Problem Statement

You are given an integer N not less than 3 and a length-N sequence of positive integers A=(A_1,A_2,\ldots,A_N).

For each k=3,4,\ldots,N, solve the following problem:

• When A_1,A_2,\ldots,A_k are sorted in descending order, find the third value from the front.

Constraints

• 3\le N\le 5\times 10^5
• 1\le A_i\le 10^9
• All input values are integers.

Sample Input 1

5
1 2 1 2 3

Sample Output 1

1
1
2

• For k=3: sorting A_1,A_2,A_3 in descending order gives 2,1,1. The third value from the front is 1, so output 1 on the first line.
• For k=4: sorting A_1,A_2,A_3,A_4 in descending order gives 2,2,1,1. The third value from the front is 1, so output 1 on the second line.
• For k=5: sorting A_1,A_2,A_3,A_4,A_5 in descending order gives 3,2,2,1,1. The third value from the front is 2, so output 2 on the third line.

Sample Input 2

10
1 1 1 3 2 5 4 3 6 5

Sample Output 2

1
1
1
2
3
3
4
5

Sample Input 3

10
11 9 1 3 17 19 10 19 17 3

Sample Output 3

1
3
9
11
11
17
17
17

Problem Statement

In the Kingdom of AtCoder, two kinds of bills are in circulation: 1-dollar bills and K-dollar bills.

At Company J's fully automated cafeteria in the kingdom, desserts and drinks are sold as products.

The company's fully automated cafeteria has a dessert vending machine that sells N desserts, and a drink vending machine that sells M drinks. The desserts are numbered 1 through N, and the drinks are numbered 1 through M.

Dessert i costs A_i dollars, and drink j costs B_j dollars.

As payment, the dessert vending machine accepts both 1-dollar bills and K-dollar bills, but the drink vending machine accepts only K-dollar bills. Both vending machines give change using only 1-dollar bills. You cannot buy two or more of the same product.

Takahashi came to Company J's fully automated cafeteria with X 1-dollar bills and Y K-dollar bills.

Among the combinations of products that he can buy with the bills he has, find the maximum number of products he can purchase.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 2 \leq K \leq 10^9
• 0 \leq X \leq 10^{15}
• 0 \leq Y \leq 10^9
• 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq B_j \leq 10^9 (1 \leq j \leq M)
• All input values are integers.

Sample Input 1

2 3 10
50 6
22 30
20 12 24

Sample Output 1

4

By shopping as follows, Takahashi can buy four products.

• Pay two 10-dollar bills to buy drink 1. No change.
• Pay two 10-dollar bills to buy drink 2. The change is eight 1-dollar bills.
• Pay two 10-dollar bills and ten 1-dollar bills to buy dessert 2. No change.
• Pay twenty-two 1-dollar bills to buy dessert 1. No change.

He cannot buy more than four products, so the answer is 4.

Sample Input 2

1 7 67
677677677766666 0
777666777
20 12 24 67 67 67 67

Sample Output 2

1

By shopping as follows, Takahashi can buy one product.

• Pay 600000777666777 1-dollar bills to buy dessert 1. The change is 600000000000000 1-dollar bills.

He cannot buy more than one product, so the answer is 1.

Sample Input 3

20 20 30
605776135 133105105
97363214 218434035 697895427 109255624 299037330 227873982 195540071 411713803 828357845 244535208 138059186 639510883 39844882 707397687 371274487 696536603 351588202 319490007 47121612 87169661
32256972 567982330 554885983 299718223 443859449 687952877 264684780 666659381 576335424 941894234 406248934 321334900 423472560 863738035 213143887 384834384 468161291 673106162 164648316 15903323

Sample Output 3

22

Problem Statement

You are given a permutation P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N) and length-M integer sequences L=(L_1,L_2,\ldots,L_M) and R=(R_1,R_2,\ldots,R_M).

For this permutation P, perform the following operation for i=1,2,\ldots,M in this order:

• Among P_{L_i},P_{L_i+1},\ldots,P_{R_i}, swap the positions of the element with the minimum value and the element with the maximum value.

Find each element of P after the M operations.

Constraints

• 2\le N\le 2\times 10^5
• 1\le M\le 2\times 10^5
• P is a permutation of (1,2,\ldots,N).
• 1\le L_i < R_i\le N
• All input values are integers.

Sample Input 1

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

Sample Output 1

3 4 2 5 1

Initially, P=(3,1,4,2,5).

• For i=1: among P_1,P_2,P_3, the minimum value is P_2 and the maximum value is P_3. Swapping P_2 and P_3 gives P=(3,4,1,2,5).
• For i=2: among P_1,P_2,P_3,P_4,P_5, the minimum value is P_3 and the maximum value is P_5. Swapping P_3 and P_5 gives P=(3,4,5,2,1).
• For i=3: among P_1,P_2,P_3,P_4, the minimum value is P_4 and the maximum value is P_3. Swapping P_3 and P_4 gives P=(3,4,2,5,1).

After the three operations, P=(3,4,2,5,1).

Sample Input 2

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

Sample Output 2

3 5 4 6 2 1

Problem Statement

There is a city represented by a grid with N rows and N columns. The cell at the i-th row from the top and j-th column from the left is denoted as cell (i,j). Each cell has one cafe.

You are planning a meeting. Among the participants, the number of people living in cell (i, j) is (A_i \times B_j) \bmod M. The travel cost for one participant living in cell (s_r,\ s_c) to go to the cafe at cell (t_r,\ t_c) is \max(|s_r - t_r|,\ |s_c - t_c|).

Let f(i, j) be the total travel cost incurred when gathering all the participants at the cafe at cell (i, j).

For each cell (i,j), find the following value, and output the bitwise XOR of these values over all cells.

• f(i,j) + (i-1)N + (j-1)

Constraints

• 1 \leq N \leq 1500
• 2 \leq M \leq 2 \times 10^6
• 1 \leq A_i \leq M-1 (1 \leq i \leq N)
• 1 \leq B_j \leq M-1 (1 \leq j \leq N)
• All input values are integers.

Sample Input 1

4 19
2 3 1 1
3 4 4 10

Sample Output 1

467

The number of participants living in each cell is as follows: \displaystyle \begin{bmatrix} 6 & 8 & 8 & 1 \\ 9 & 12 & 12 & 11 \\ 3 & 4 & 4 & 10 \\ 3 & 4 & 4 & 10 \end{bmatrix}.

For example, the value of f(1,2) is obtained as the sum 176 of the following 16 values:

• The total amount 6 \times 1 = 6 paid by the 6 residents of cell (1,1), each of whom pays a travel cost of \max(|1 - 1|,\ |1 - 2|) = 1
• The total amount 8 \times 0 = 0 paid by the 8 residents of cell (1,2), each of whom pays a travel cost of \max(|1 - 1|,\ |2 - 2|) = 0
• The total amount 8 \times 1 = 8 paid by the 8 residents of cell (1,3), each of whom pays a travel cost of \max(|1 - 1|,\ |3 - 2|) = 1
• The total amount 1 \times 2 = 2 paid by the 1 resident of cell (1,4), each of whom pays a travel cost of \max(|1 - 1|,\ |4 - 2|) = 2
• \vdots
• The total amount 3 \times 3 = 9 paid by the 3 residents of cell (4,1), each of whom pays a travel cost of \max(|4 - 1|,\ |1 - 2|) = 3
• The total amount 4 \times 3 = 12 paid by the 4 residents of cell (4,2), each of whom pays a travel cost of \max(|4 - 1|,\ |2 - 2|) = 3
• The total amount 4 \times 3 = 12 paid by the 4 residents of cell (4,3), each of whom pays a travel cost of \max(|4 - 1|,\ |3 - 2|) = 3
• The total amount 10 \times 3 = 30 paid by the 10 residents of cell (4,4), each of whom pays a travel cost of \max(|4 - 1|,\ |4 - 2|) = 3

The value of f(i,j) for each cell is as follows: \displaystyle \begin{bmatrix} 220 & 176 & 179 & 224 \\ 199 & 140 & 136 & 182 \\ 212 & 159 & 143 & 178 \\ 255 & 215 & 201 & 218 \end{bmatrix}.

Sample Input 2

6 67
1 6 9 2 3 1
1 10 3 7 2 2

Sample Output 2

1021

Sample Input 3

20 676767
60932 508200 22883 481150 426836 554098 276223 307959 133025 573906 17711 413230 274246 500277 524959 477728 546547 43099 324227 660187
552697 293978 246000 159233 213736 628198 394200 194076 618720 453035 615100 331522 669419 180856 530693 399531 223149 159334 102107 598633

Sample Output 3

764668547

Problem Statement

You are given positive integers L and R satisfying L\le R.

A sequence of positive integers A=(A_L,A_{L+1},\ldots,A_R) of length R-L+1 satisfying the following condition is called a good integer sequence:

• For every pair of integers (i,j) satisfying L\le i < j\le R, if A_i = A_j, then \operatorname{popcount}(i)<\operatorname{popcount}(j).

Find the minimum value of \max(A_L,A_{L+1},\ldots,A_R) over all good integer sequences A=(A_L,A_{L+1},\ldots,A_R).

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

Constraints

• 1\le T\le 10^4
• 1\le L \le R\le 10^{18}
• All input values are integers.

Sample Input 1

5
3 6
1 1
2 15
100 10000000
514284786278117031 620546740167642909

Sample Output 1

3
1
6
1636985
11375123021856567

Consider the first test case.

(A_3,A_4,A_5,A_6)=(1,2,2,3) is a good integer sequence, and \max(A_3,A_4,A_5,A_6)=3.

There is no good integer sequence with \max(A_3,A_4,A_5,A_6) < 3, so output 3 on the first line.