Problem Statement

There is a programming contest with N problems. For each i = 1, 2, \ldots, N, the score for the i-th problem is S_i.

Print the total score for all problems with a score of X or less.

Constraints

• All input values are integers.
• 4 \leq N \leq 8
• 100 \leq S_i \leq 675
• 100 \leq X \leq 675

Sample Input 1

6 200
100 675 201 200 199 328

Sample Output 1

499

Three problems have a score of 200 or less: the first, fourth, and fifth, for a total score of S_1 + S_4 + S_5 = 100 + 200 + 199 = 499.

Sample Input 2

8 675
675 675 675 675 675 675 675 675

Sample Output 2

5400

Sample Input 3

8 674
675 675 675 675 675 675 675 675

Sample Output 3

0

Problem Statement

You are given a string S of length N consisting of lowercase English letters, along with lowercase English letters c_1 and c_2.

Find the string obtained by replacing every character of S that is not c_1 with c_2.

Constraints

• 1\le N\le 100
• N is an integer.
• c_1 and c_2 are lowercase English letters.
• S is a string of length N consisting of lowercase English letters.

Sample Input 1

3 b g
abc

Sample Output 1

gbg

Replacing a and c (which are not b) with g in S= abc results in gbg, so print gbg.

Sample Input 2

1 s h
s

Sample Output 2

s

It is possible that the resulting string after replacement is the same as the original string.

Sample Input 3

7 d a
atcoder

Sample Output 3

aaaadaa

Sample Input 4

10 b a
acaabcabba

Sample Output 4

aaaabaabba

Problem Statement

You are given N strings S_1,S_2,\ldots,S_N consisting of lowercase English letters.
Determine if there are distinct integers i and j between 1 and N, inclusive, such that the concatenation of S_i and S_j in this order is a palindrome.

A string T of length M is a palindrome if and only if the i-th character and the (M+1-i)-th character of T are the same for every 1\leq i\leq M.

Constraints

• 2\leq N\leq 100
• 1\leq \lvert S_i\rvert \leq 50
• N is an integer.
• S_i is a string consisting of lowercase English letters.
• All S_i are distinct.

Sample Input 1

5
ab
ccef
da
a
fe

Sample Output 1

Yes

If we take (i,j)=(1,4), the concatenation of S_1=ab and S_4=a in this order is aba, which is a palindrome, satisfying the condition.
Thus, print Yes.

Here, we can also take (i,j)=(5,2), for which the concatenation of S_5=fe and S_2=ccef in this order is feccef, satisfying the condition.

Sample Input 2

3
a
b
aba

Sample Output 2

No

No two distinct strings among S_1, S_2, and S_3 form a palindrome when concatenated. Thus, print No.
Note that the i and j in the statement must be distinct.

Sample Input 3

2
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

Sample Output 3

Yes

Problem Statement

You are given an integer sequence A=(A_1,A_2,\ldots,A_N) of length N. Here, each element of A is either -1 or an integer between 1 and N, inclusive.

Determine whether there exists an integer sequence P=(P_1,P_2,\ldots,P_N) of length N that satisfies all of the following conditions, and if it exists, find one.

• P is a permutation of (1,2,\ldots,N).
• For i=1,2,\ldots,N, if A_i \neq -1, then P_i=A_i holds.

Constraints

• 1\le N\le 10
• A_i=-1 or 1\le A_i \le N
• All input values are integers.

Sample Input 1

4
-1 -1 2 -1

Sample Output 1

Yes
3 1 2 4

P=(3,1,2,4) satisfies all conditions.

Besides this, P=(1,3,2,4) or P=(4,3,2,1) also satisfies all conditions.

Sample Input 2

5
-1 -1 1 -1 1

Sample Output 2

No

There is no P that satisfies all conditions.

Sample Input 3

7
3 -1 4 -1 5 -1 2

Sample Output 3

Yes
3 7 4 1 5 6 2

Problem Statement

There is an empty integer sequence A=(). You are given Q queries, and you need to process them in the given order. There are two types of queries:

• Type 1: Given in the format 1 c x. Add c copies of x to the end of A.
• Type 2: Given in the format 2 k. Remove the first k elements from A and output the sum of the removed k integers. It is guaranteed that k is at most the length of A at that time.

Constraints

• 1 \leq Q \leq 2 \times 10^{5}
• In type 1 queries, 1 \leq c \leq 10^{9}.
• In type 1 queries, 1 \leq x \leq 10^{9}.
• In type 2 queries, letting n be the length of A at that time, 1 \leq k \leq \min(10^{9},n).
• All input values are integers.

Sample Input 1

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

Sample Output 1

11
19

• 1st query: Add 2 copies of 3 to the end of A. Then, A=(3,3).
• 2nd query: Add 4 copies of 5 to the end of A. Then, A=(3,3,5,5,5,5).
• 3rd query: Remove the first 3 elements from A. Then, the sum of the removed 3 integers is 3+3+5=11, so output 11. After removal, A=(5,5,5).
• 4th query: Add 6 copies of 2 to the end of A. Then, A=(5,5,5,2,2,2,2,2,2).
• 5th query: Remove the first 5 elements from A. Then, the sum of the removed 5 integers is 5+5+5+2+2=19, so output 19. After removal, A=(2,2,2,2).

Sample Input 2

10
1 75 22
1 81 72
1 2 97
1 84 82
1 2 32
1 39 57
2 45
1 40 16
2 32
2 42

Sample Output 2

990
804
3024

Sample Input 3

10
1 160449218 954291757
2 17217760
1 353195922 501899080
1 350034067 910748511
1 824284691 470338674
2 180999835
1 131381221 677959980
1 346948152 208032501
1 893229302 506147731
2 298309896

Sample Output 3

16430766442004320
155640513381884866
149721462357295680

Problem Statement

There is a single integer N written on a blackboard.
Takahashi will repeat the following series of operations until all integers not less than 2 are removed from the blackboard:

• Choose one integer x not less than 2 written on the blackboard.
• Erase one occurrence of x from the blackboard. Then, write two new integers \left \lfloor \dfrac{x}{2} \right\rfloor and \left\lceil \dfrac{x}{2} \right\rceil on the blackboard.
• Takahashi must pay x yen to perform this series of operations.

Here, \lfloor a \rfloor denotes the largest integer not greater than a, and \lceil a \rceil denotes the smallest integer not less than a.

What is the total amount of money Takahashi will have paid when no more operations can be performed?
It can be proved that the total amount he will pay is constant regardless of the order in which the operations are performed.

Constraints

• 2 \leq N \leq 10^{17}

Sample Input 1

3

Sample Output 1

5

Here is an example of how Takahashi performs the operations:

• Initially, there is one 3 written on the blackboard.
• He chooses 3. He pays 3 yen, erases one 3 from the blackboard, and writes \left \lfloor \dfrac{3}{2} \right\rfloor = 1 and \left\lceil \dfrac{3}{2} \right\rceil = 2 on the blackboard.
• There is one 2 and one 1 written on the blackboard.
• He chooses 2. He pays 2 yen, erases one 2 from the blackboard, and writes \left \lfloor \dfrac{2}{2} \right\rfloor = 1 and \left\lceil \dfrac{2}{2} \right\rceil = 1 on the blackboard.
• There are three 1s written on the blackboard.
• Since all integers not less than 2 have been removed from the blackboard, the process is finished.

Takahashi has paid a total of 3 + 2 = 5 yen for the entire process, so print 5.

Sample Input 2

340

Sample Output 2

2888

Sample Input 3

100000000000000000

Sample Output 3

5655884811924144128

Problem Statement

There is an election to choose one winner from N candidates with candidate numbers 1, 2, \ldots, N, and there have been M votes cast.

Each vote is for exactly one candidate, with the i-th vote being for candidate A_i.

The votes will be counted in order from first to last, and after each vote is counted, the current winner will be updated and displayed.

The candidate with the most votes among those counted is the winner. If there are multiple candidates with the most votes, the one with the smallest candidate number is the winner.

For each i = 1, 2, \ldots, M, determine the winner when counting only the first i votes.

Constraints

• 1 \leq N, M \leq 200000
• 1 \leq A_i \leq N
• All input values are integers.

Sample Input 1

3 7
1 2 2 3 1 3 3

Sample Output 1

1
1
2
2
1
1
3

Let C_i denote the number of votes for candidate i.

• After the first vote is counted, (C_1, C_2, C_3) = (1, 0, 0), so the winner is 1.
• After the second vote is counted, (C_1, C_2, C_3) = (1, 1, 0), so the winner is 1.
• After the third vote is counted, (C_1, C_2, C_3) = (1, 2, 0), so the winner is 2.
• After the fourth vote is counted, (C_1, C_2, C_3) = (1, 2, 1), so the winner is 2.
• After the fifth vote is counted, (C_1, C_2, C_3) = (2, 2, 1), so the winner is 1.
• After the sixth vote is counted, (C_1, C_2, C_3) = (2, 2, 2), so the winner is 1.
• After the seventh vote is counted, (C_1, C_2, C_3) = (2, 2, 3), so the winner is 3.

Sample Input 2

100 5
100 90 80 70 60

Sample Output 2

100
90
80
70
60

Sample Input 3

9 8
8 8 2 2 8 8 2 2

Sample Output 3

8
8
8
2
8
8
8
2

Problem Statement

You are given a sequence A=(A_0,A_1,\ldots,A_{N-1}) of length N.
There is an initially empty dish. Takahashi is going to repeat the following operation K times.

• Let X be the number of candies on the dish. He puts A_{(X\bmod N)} more candies on the dish. Here, X\bmod N denotes the remainder when X is divided by N.

Find how many candies are on the dish after the K operations.

Constraints

• 2 \leq N \leq 2\times 10^5
• 1 \leq K \leq 10^{12}
• 1 \leq A_i\leq 10^6
• All values in input are integers.

Sample Input 1

5 3
2 1 6 3 1

Sample Output 1

11

The number of candies on the dish transitions as follows.

• In the 1-st operation, we have X=0, so A_{(0\mod 5)}=A_0=2 more candies will be put on the dish.
• In the 2-nd operation, we have X=2, so A_{(2\mod 5)}=A_2=6 more candies will be put on the dish.
• In the 3-rd operation, we have X=8, so A_{(8\mod 5)}=A_3=3 more candies will be put on the dish.

Thus, after the 3 operations, there will be 11 candies on the dish. Note that you must not print the remainder divided by N.

Sample Input 2

10 1000000000000
260522 914575 436426 979445 648772 690081 933447 190629 703497 47202

Sample Output 2

826617499998784056

The answer may not fit into a 32-bit integer type.

Problem Statement

There are N Christmas trees on a two-dimensional plane. The i-th (1\le i\le N) Christmas tree is located at coordinates (X_i,Y_i).

You are given Q queries. Process the queries in order. Each query is one of the following:

• Type 1 : Given in the form 1 i x y. Change the coordinates of the i-th Christmas tree to (x,y).
• Type 2 : Given in the form 2 L R x y. Output the Manhattan distance from the coordinates (x,y) to the farthest Christmas tree among the L,L+1,\ldots,R-th Christmas trees.

Here, the Manhattan distance between coordinates (x_1,y_1) and coordinates (x_2,y_2) is defined as |x_1-x_2|+|y_1-y_2|.

Constraints

• 1\le N,Q\le 2\times 10^5
• -10^9\le X_i,Y_i\le 10^9
• 1\le i\le N
• 1\le L\le R\le N
• -10^9\le x,y\le 10^9
• All input values are integers.

Sample Input 1

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

Sample Output 1

3
3
2

Initially, the 1st, 2nd, 3rd Christmas trees are located at coordinates (-1,-1), (1,2), (-2,1), respectively.

Each query is processed as follows:

• The Manhattan distances from the 1st and 2nd Christmas trees to coordinates (0,0) are 2 and 3, respectively. Thus, output 3, which is the maximum value among 2,3.
• The Manhattan distances from the 1st, 2nd, 3rd Christmas trees to coordinates (-1,2) are 3, 2, 2, respectively. Thus, output 3, which is the maximum value among 3,2,2.
• Change the coordinates of the 1st Christmas tree to (0,1). The coordinates of the 1st, 2nd, 3rd Christmas trees become (0,1),(1,2),(-2,1), respectively.
• The Manhattan distances from the 1st, 2nd, 3rd Christmas trees to coordinates (-1,2) are 2, 2, 2, respectively. Thus, output 2, which is the maximum value among 2,2,2.

Sample Input 2

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

Sample Output 2

24
24
22
30
9