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

AtCoder Regular Contest (ARC) is divided into two divisions.

• In ARC Div. 1, participants whose rating at the start of the contest is between 1600 and 2799, inclusive, are subject to rating updates.
• In ARC Div. 2, participants whose rating at the start of the contest is between 1200 and 2399, inclusive, are subject to rating updates.

Takahashi decided to participate in N ARCs.

Initially, his rating is R.

The i-th (1\leq i\leq N) ARC is Div. D _ i, and his performance in that contest is represented by an integer A _ i.

If he is subject to a rating update in the i-th ARC, let T be his rating at the start of that contest. Then, after the contest, his rating becomes T+A _ i.

If his is not subject to a rating update, his rating does not change.

Rating updates for ARCs are performed immediately after the contest ends, and whether he is subject to rating updates in the next contest is determined based on his rating after the update.

Find his rating after finishing the N ARCs.

He does not participate in any contests other than these N ARCs, and his rating does not change in other ways.

Constraints

• 1\leq N\leq 100
• 0\leq R\leq 4229
• 1\leq D _ i\leq 2\ (1\leq i\leq N)
• -1000\leq A _ i\leq 1000\ (1\leq i\leq N)
• All input values are integers.

Sample Input 1

4 1255
2 900
1 521
2 600
1 52

Sample Output 1

2728

Initially, Takahashi's rating is 1255.

For each contest, Takahashi's rating changes as follows:

• The 1st ARC is Div. 2. He is subject to rating updates, so his rating becomes 1255+900=2155.
• The 2nd ARC is Div. 1. He is subject to rating updates, so his rating becomes 2155+521=2676.
• The 3rd ARC is Div. 2. He is not subject to rating updates, so his rating does not change.
• The 4th ARC is Div. 1. He is subject to rating updates, so his rating becomes 2676+52=2728.

After the four ARCs, his rating is 2728, so print 2728.

Sample Input 2

2 3031
1 1000
2 -1000

Sample Output 2

3031

He is a Red coder, so his rating does not change upon his performance in ARC.

Sample Input 3

15 2352
2 -889
2 420
2 -275
1 957
1 -411
1 -363
1 151
2 -193
2 289
2 -770
2 109
1 345
2 551
1 -702
1 355

Sample Output 3

1226

Problem Statement

Takahashi decided to hold a programming contest.

The contest consists of five problems: A, B, C, D, E, with scores a, b, c, d, e, respectively.

There are 31 participants, and all of them solved at least one problem.

More specifically, for every non-empty subsequence (not necessarily contiguous) of the string ABCDE, there is a participant named after that subsequence who solved the problems corresponding to the letters in their name and did not solve the other problems.

For example, participant A solved only problem A, and participant BCE solved problems B, C, and E.

Print the names of the participants in order of their obtained scores, from the largest to the smallest. The score obtained by a participant is the sum of the scores of the problems they solved.

If two participants obtained the same score, print the one whose name is lexicographically smaller first.

Constraints

• 100\leq a\leq b\leq c\leq d\leq e\leq 2718
• All input values are integers.

Sample Input 1

400 500 600 700 800

Sample Output 1

ABCDE
BCDE
ACDE
ABDE
ABCE
ABCD
CDE
BDE
ADE
BCE
ACE
BCD
ABE
ACD
ABD
ABC
DE
CE
BE
CD
AE
BD
AD
BC
AC
AB
E
D
C
B
A

The score of each participant is as follows:

For example, ADE and BCE obtained the same score, and ADE is lexicographically smaller, so print ADE before BCE.

Sample Input 2

800 800 900 900 1000

Sample Output 2

ABCDE
ACDE
BCDE
ABCE
ABDE
ABCD
CDE
ACE
ADE
BCE
BDE
ABE
ACD
BCD
ABC
ABD
CE
DE
AE
BE
CD
AC
AD
BC
BD
AB
E
C
D
A
B

Sample Input 3

128 256 512 1024 2048

Sample Output 3

ABCDE
BCDE
ACDE
CDE
ABDE
BDE
ADE
DE
ABCE
BCE
ACE
CE
ABE
BE
AE
E
ABCD
BCD
ACD
CD
ABD
BD
AD
D
ABC
BC
AC
C
AB
B
A

Problem Statement

You are given the first N terms A _ 1,A _ 2,\dotsc,A _ N of an infinite sequence A=(A _ 1,A _ 2,A _ 3,\dotsc) that has period N.

Determine if there exists a non-empty contiguous subsequence of this infinite sequence whose sum is S.

Here, an infinite sequence A has period N when A _ i=A _ {i-N} for every integer i>N.

Constraints

• 1\leq N\leq2\times10 ^ 5
• 1\leq A _ i\leq 10 ^ 9
• 1\leq S\leq 10 ^ {18}
• All input values are integers.

Sample Input 1

3 42
3 8 4

Sample Output 1

Yes

The sequence A is (3,8,4,3,8,4,3,8,4,\dotsc).

For the subsequence (A _ 2,A _ 3,A _ 4,A _ 5,A _ 6,A _ 7,A _ 8,A _ 9)=(8,4,3,8,4,3,8,4), we have 8+4+3+8+4+3+8+4=42, so print Yes.

Sample Input 2

3 1
3 8 4

Sample Output 2

No

All elements of A are at least 3, so the sum of any non-empty contiguous subsequence is at least 3.

Thus, there is no subsequence with sum 1, so print No.

Sample Input 3

20 83298426
748 169 586 329 972 529 432 519 408 587 138 249 656 114 632 299 984 755 404 772

Sample Output 3

Yes

Sample Input 4

20 85415869
748 169 586 329 972 529 432 519 408 587 138 249 656 114 632 299 984 755 404 772

Sample Output 4

No

Problem Statement

There is a grid with H horizontal rows and W vertical columns. Let (i, j) denote the cell at the i-th row (1\leq i\leq H) from the top and j-th column (1\leq j\leq W) from the left.

Initially, there is a slime with strength S _ {i,j} in cell (i,j), and Takahashi is the slime in the cell (P,Q).

Find the maximum possible strength of Takahashi after performing the following action any number of times (possibly zero):

• Among the slimes adjacent to him, choose one whose strength is strictly less than \dfrac{1}{X} times his strength and absorb it. As a result, the absorbed slime disappears, and Takahashi's strength increases by the strength of the absorbed slime.

When performing the above action, the gap left by the disappeared slime is immediately filled by Takahashi, and the slimes that were adjacent to the disappeared one (if any) become newly adjacent to Takahashi (refer to the explanation in sample 1).

Constraints

• 1\leq H,W\leq500
• 1\leq P\leq H
• 1\leq Q\leq W
• 1\leq X\leq10^9
• 1\leq S _ {i,j}\leq10^{12}
• All input values are integers.

Sample Input 1

3 3 2
2 2
14 6 9
4 9 20
17 15 7

Sample Output 1

28

Initially, the strength of the slime in each cell is as follows:

For example, Takahashi can act as follows:

• Absorb the slime in cell (2,1). His strength becomes 9+4=13, and the slimes in cells (1,1) and (3,1) become newly adjacent to him.
• Absorb the slime in cell (1,2). His strength becomes 13+6=19, and the slime in cell (1,3) becomes newly adjacent to him.
• Absorb the slime in cell (1,3). His strength becomes 19+9=28.

After these actions, his strength is 28.

No matter how he acts, it is impossible to get a strength greater than 28, so print 28.

Note that Takahashi can only absorb slimes whose strength is strictly less than half of his strength. For example, in the figure on the right above, he cannot absorb the slime in cell (1,1).

Sample Input 2

3 4 1
1 1
5 10 1 1
10 1 1 1
1 1 1 1

Sample Output 2

5

He cannot absorb any slimes.

Sample Input 3

8 10 2
1 5
388 130 971 202 487 924 247 286 237 316
117 166 918 106 336 928 493 391 235 398
124 280 425 955 212 988 227 222 307 226
336 302 478 246 950 368 291 236 170 101
370 200 204 141 287 410 388 314 205 460
291 104 348 337 404 399 416 263 415 339
105 420 302 334 231 481 466 366 401 452
119 432 292 403 371 417 351 231 482 184

Sample Output 3

1343

Problem Statement

For a positive integer x, define f(x) as follows: "While x is even, keep dividing it by 2. The final value of x after these divisions is f(x)." For example, f(4)=f(2)=f(1)=1, and f(12)=f(6)=f(3)=3.

Given an integer sequence A=(A_1,A_2,\ldots,A_N) of length N, find \displaystyle \sum_{i=1}^N \sum_{j=i}^N f(A_i+A_j).

Constraints

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

Sample Input 1

2
4 8

Sample Output 1

5

f(A_1+A_1)=f(8)=1, f(A_1+A_2)=f(12)=3, f(A_2+A_2)=f(16)=1. Thus, Print 1+3+1=5.

Sample Input 2

3
51 44 63

Sample Output 2

384

Sample Input 3

8
577752 258461 183221 889769 278633 577212 392309 326001

Sample Output 3

20241214

Problem Statement

You are given integer sequences A=(A_1,A_2,\ldots,A_N) and B=(B_1,B_2,\ldots,B_N) of length N, and integer sequences X=(X_1,X_2,\ldots,X_K) and Y=(Y_1,Y_2,\ldots,Y_K) of length K.

For each k=1,2,\ldots,K, find \displaystyle \sum_{i=1}^{X_k} \sum_{j=1}^{Y_k} |A_i-B_j|.

Constraints

• 1\le N\le 10^5
• 0\le A_i,B_j\le 2\times 10^8
• 1\le K\le 10^4
• 1\le X_k,Y_k\le N
• All input values are integers.

Sample Input 1

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

Sample Output 1

1
4
2
6

For k=1, the answer is |A_1-B_1|=1, so print 1 on the first line.

For k=2, the answer is |A_1-B_1|+|A_1-B_2|=1+3=4, so print 4 on the second line.

For k=3, the answer is |A_1-B_1|+|A_2-B_1|=1+1=2, so print 2 on the third line.

For k=4, the answer is |A_1-B_1|+|A_1-B_2|+|A_2-B_1|+|A_2-B_2|=1+3+1+1=6, so print 6 on the fourth line.

Sample Input 2

5
1163686 28892 1263085 2347878 520306
1332157 1202905 2437161 1291976 563395
5
5 3
1 5
2 3
1 2
5 5

Sample Output 2

13331322
2209746
6366712
207690
20241215