Problem Statement

Given integers A and B, print the value A^B.

Constraints

• 1 \leq A, B \leq 9
• All values in the input are integers.

Sample Input 1

4 3

Sample Output 1

64

4^3 = 64, so 64 should be printed.

Sample Input 2

5 5

Sample Output 2

3125

Sample Input 3

8 1

Sample Output 3

8

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

Takahashi has a calculator that initially displays 1.
He will perform N operations on the calculator.
In the i-th operation (1 \leq i \leq N), he multiplies the currently displayed number by a positive integer A_i.
However, the calculator can display at most K digits. If the result of the multiplication has (K+1) or more digits, the display shows 1 instead; otherwise, the result is shown correctly.

Find the number showing on the calculator after the N operations.

Constraints

• 1 \leq N \leq 100
• 1 \leq K \leq 18
• 1 \leq A_i < 10^K
• All input values are integers.

Sample Input 1

5 2
7 13 3 2 5

Sample Output 1

10

This calculator can display at most two digits and initially shows 1. Takahashi operates as follows:

• The 1st operation multiplies by 7. Since 1 \times 7 = 7, the calculator shows 7.
• The 2nd operation multiplies by 13. Since 7 \times 13 = 91, the calculator shows 91.
• The 3rd operation multiplies by 3. Since 91\times 3=273, which has three digits, the calculator shows 1.
• The 4th operation multiplies by 2. Since 1\times 2=2, the calculator shows 2.
• The 5th operation multiplies by 5. Since 2\times 5=10, the calculator shows 10.

Sample Input 2

2 1
2 5

Sample Output 2

1

Problem Statement

Takahashi ate N plates of sushi at a sushi restaurant. The color of the i-th plate is represented by a string C_i.

The price of a sushi corresponds to the color of the plate. For each i=1,\ldots,M, the sushi on a plate whose color is represented by a string D_i is worth P_i yen a plate (yen is the currency of Japan). If the color does not coincide with any of D_1,\ldots, and D_M, it is worth P_0 yen a plate.

Find the total amount of the prices of sushi that Takahashi ate.

Constraints

• 1\leq N,M\leq 100
• C_i and D_i are strings of length between 1 and 20, inclusive, consisting of lowercase English letters.
• D_1,\ldots, and D_M are distinct.
• 1\leq P_i\leq 10000
• N, M, and P_i are integers.

Sample Input 1

3 2
red green blue
blue red
800 1600 2800

Sample Output 1

5200

A blue plate, red plate, and green plate are worth P_1 = 1600, P_2 = 2800, and P_0 = 800 yen, respectively.

The total amount of the prices of the sushi that he ate is 2800+800+1600=5200 yen.

Sample Input 2

3 2
code queen atcoder
king queen
10 1 1

Sample Output 2

21

Problem Statement

You are given an integer sequence A=(A_1,A_2,\ldots,A_N) of length N.

You can perform the following operation zero or more times in any order:

• Choose an integer k between 1 and |A|-3, inclusive, such that A_k=A_{k+1}=A_{k+2}=A_{k+3}, and remove A_k,A_{k+1},A_{k+2},A_{k+3} from A. (More formally, replace A with (A_1,A_2,\ldots,A_{k-1},A_{k+4},A_{k+5},\ldots,A_N).)

Here, |A| represents the length of the integer sequence A.

Find the minimum possible value of the final |A| after repeating the operation.

Constraints

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

Sample Input 1

10
1 1 1 4 4 4 4 1 2 3

Sample Output 1

2

You can make |A|=2 with two operations as follows:

• Choose k=4. This choice is valid since A_4=A_5=A_6=A_7=4 holds. A=(1,1,1,1,2,3) is obtained.
• Choose k=1. This choice is valid since A_1=A_2=A_3=A_4=1 holds. A=(2,3) is obtained.

It is impossible to make |A| less than 2, so output 2.

Sample Input 2

3
2 1 3

Sample Output 2

3

You cannot perform any operation from the beginning.

Sample Input 3

13
1 1 4 4 4 1 1 1 1 4 1 4 1

Sample Output 3

5

Problem Statement

You are given an integer sequence A=(A_1,A_2,\dots,A_N). You can perform the following operation any number of times (possibly zero).

• Choose integers i and j with 1\leq i,j \leq N. Decrease A_i by one and increase A_j by one.

Find the minimum number of operations required to make the difference between the minimum and maximum values of A at most one.

Constraints

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

Sample Input 1

4
4 7 3 7

Sample Output 1

3

By the following three operations, the difference between the minimum and maximum values of A becomes at most one.

• Choose i=2 and j=3 to make A=(4,6,4,7).
• Choose i=4 and j=1 to make A=(5,6,4,6).
• Choose i=4 and j=3 to make A=(5,6,5,5).

You cannot make the difference between maximum and minimum values of A at most one by less than three operations, so the answer is 3.

Sample Input 2

1
313

Sample Output 2

0

Sample Input 3

10
999999997 999999999 4 3 2 4 999999990 8 999999991 999999993

Sample Output 3

2499999974

Problem Statement

Given integers N and M, compute the sum \displaystyle \sum_{k=0}^{N} \rm{popcount}(k \mathbin{\&} M), modulo 998244353.

Here, \mathbin{\&} represents the bitwise \rm{AND} operation.

Constraints

• N is an integer between 0 and 2^{60} - 1, inclusive.
• M is an integer between 0 and 2^{60} - 1, inclusive.

Sample Input 1

4 3

Sample Output 1

4

• \rm{popcount}(0\mathbin{\&}3) = 0
• \rm{popcount}(1\mathbin{\&}3) = 1
• \rm{popcount}(2\mathbin{\&}3) = 1
• \rm{popcount}(3\mathbin{\&}3) = 2
• \rm{popcount}(4\mathbin{\&}3) = 0

The sum of these values is 4.

Sample Input 2

0 0

Sample Output 2

0

It is possible that N = 0 or M = 0.

Sample Input 3

1152921504606846975 1152921504606846975

Sample Output 3

499791890

Remember to compute the result modulo 998244353.

Problem Statement

AtCoder in another world holds 10 types of contests called AAC, ..., AJC. There will be N contests from now on.
The types of these N contests are given to you as a string S: if the i-th character of S is x, the i-th contest will be AxC.
AtCoDeer will choose and participate in one or more contests from the N so that the following condition is satisfied.

• In the sequence of contests he will participate in, the contests of the same type are consecutive.
  • Formally, when AtCoDeer participates in x contests and the i-th of them is of type T_i, for every triple of integers (i,j,k) such that 1 \le i < j < k \le x, T_i=T_j must hold if T_i=T_k.

Find the number of ways for AtCoDeer to choose contests to participate in, modulo 998244353.
Two ways to choose contests are considered different when there is a contest c such that AtCoDeer participates in c in one way but not in the other.

Constraints

• 1 \le N \le 1000
• |S|=N
• S consists of uppercase English letters from A through J.

Sample Input 1

4
BGBH

Sample Output 1

13

For example, participating in the 1-st and 3-rd contests is valid, and so is participating in the 2-nd and 4-th contests.
On the other hand, participating in the 1-st, 2-nd, 3-rd, and 4-th contests is invalid, since the participations in ABCs are not consecutive, violating the condition for the triple (i,j,k)=(1,2,3).
Additionally, it is not allowed to participate in zero contests.
In total, there are 13 valid ways to participate in some contests.

Sample Input 2

100
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBIEIJEIJIJCGCCFGIEBIHFCGFBFAEJIEJAJJHHEBBBJJJGJJJCCCBAAADCEHIIFEHHBGF

Sample Output 2

330219020

Be sure to find the count modulo 998244353.

Problem Statement

You are given N, Q, and A=(A_1,\ldots,A_N).
Process Q queries, each of which is of one of the following two kinds:

• 1 x v: update A_x to v.
• 2 x: let B_i=\sum_{j=1}^{i}A_j, C_i=\sum_{j=1}^{i}B_j, and D_i=\sum_{j=1}^{i}C_j. Print D_x modulo 998244353.

Constraints

• 1 \leq N \leq 2\times10^5
• 1 \leq Q \leq 2\times10^5
• 0 \leq A_i \leq 10^9
• 1 \leq x \leq N
• 0 \leq v \leq 10^9
• All values in input are integers.

Sample Input 1

3 3
1 2 3
2 3
1 2 0
2 3

Sample Output 1

15
9

When the 1-st query is given, A=(1,2,3), so B=(1,3,6), C=(1,4,10), and D=(1,5,15); thus, D_3=15.

When the 3-rd query is given, A=(1,0,3), so B=(1,1,4), C=(1,2,6), and D=(1,3,9); thus, D_3=9.

Sample Input 2

2 1
998244353 998244353
2 1

Sample Output 2

0