Problem Statement

There is a rectangular chocolate bar divided into a grid with 30 rows and 30 columns, where each cell corresponds to one piece of chocolate.

The following operations are performed on this chocolate bar in order.

• Perform the operation of removing the bottommost row B times.
• Perform the operation of removing the rightmost column R times.

How many pieces of chocolate remain in the chocolate bar after all operations are finished?

Constraints

• All input values are integers.
• 1 \le B,R \le 29

Sample Input 1

8 8

Sample Output 1

484

• First, the operation of removing the bottommost row is performed 8 times.
  • After this, the chocolate bar has 22 rows and 30 columns.
• Then, the operation of removing the rightmost column is performed 8 times.
  • After this, the chocolate bar has 22 rows and 22 columns.
• The number of remaining pieces of chocolate is 484.

Sample Input 2

10 24

Sample Output 2

120

Sample Input 3

21 7

Sample Output 3

207

Problem Statement

You are playing nine-ball, a billiards game.

This game uses a total of 9 balls, one for each number from 1 to 9.
Currently, K balls remain on the table, and their numbers are A_1,A_2,\dots,A_K.
It is now your turn, and you must aim at the lowest-numbered ball remaining on the table. However, if the ball numbered 9 is no longer on the table, the game has already ended.

Print the number of the ball you should aim at on your turn. However, if the ball numbered 9 is not on the table, the game has already ended, so print -1 instead.

Constraints

• All input values are integers.
• 1 \le K \le 9
• 1 \le A_i \le 9
• The values A_i are distinct.

Sample Input 1

5
6 4 2 9 8

Sample Output 1

2

The balls numbered 2,4,6,8,9 remain on the table, and the ball you should aim at next is the one numbered 2.

Sample Input 2

4
8 2 4 6

Sample Output 2

-1

The balls numbered 2,4,6,8 remain on the table, but the ball numbered 9 does not.
In this case, the game has already ended, so the answer is -1.

Sample Input 3

3
7 9 6

Sample Output 3

6

Problem Statement

You are given sequences A=(A _ 1,A _ 2,\ldots,A _ N) and B=(B _ 1,B _ 2,\ldots,B _ N) of length N consisting of positive integers.

The following operation is performed on the sequence A exactly once.

• Choose one element of A, take it out, and insert it at any position in the remaining sequence. More formally, perform the following two steps in order.
  • Choose an integer i satisfying 1\le i\le N, let the sequence X=(X _ 1,X _ 2,\ldots,X _ {N-1}) of length N-1 be (A _ 1,A _ 2,\ldots,A _ {i-1},A _ {i+1},A _ {i+2},\ldots,A _ N), and let the integer Y be A _ i.
  • Choose an integer j satisfying 1\le j\le N, and let the sequence (X _ 1,X _ 2,\ldots,X _ {j-1},Y,X _ j,X _ {j+1},\ldots,X _ {N-1}) of length N be the new A.

Note that the element may be inserted at the left end or the right end of the sequence.

Determine whether it is possible to make A equal to B after the operation.

Constraints

• 1\le N\le2\times10 ^ 5
• 1\le A _ i\le N\ (1\le i\le N)
• 1\le B _ i\le N\ (1\le i\le N)
• All input values are integers.

Sample Input 1

6
1 4 1 4 2 1
1 4 1 1 4 2

Sample Output 1

Yes

For example, by taking out A _ 6 and inserting it between the 3-rd and 4-th elements of the remaining sequence, A after the operation becomes (1,4,1,1,4,2).

Thus, print Yes.

Sample Input 2

2
1 1
1 2

Sample Output 2

No

No matter what operation is performed on A, it cannot be made equal to B.

Sample Input 3

3
1 2 3
1 2 3

Sample Output 3

Yes

The element taken out may be inserted back at its original position.

Sample Input 4

30
25 11 21 15 30 20 17 19 17 21 10 13 22 10 22 14 30 25 17 25 11 19 27 27 15 18 16 16 20 16
25 11 15 30 20 17 19 17 21 10 13 22 10 22 14 30 25 17 25 11 19 27 27 15 21 18 16 16 20 16

Sample Output 4

Yes

Problem Statement

You are given a sequence A=(A _ 1,A _ 2,\ldots,A _ N) of length N consisting of positive integers.

The following operation is performed on the sequence A exactly once.

• Choose one element of A, take it out, and insert it into the remaining sequence at its original position or earlier. More formally, perform the following two steps in order.
  • Choose an integer i satisfying 1\le i\le N, let the sequence X=(X _ 1,X _ 2,\ldots,X _ {N-1}) of length N-1 be (A _ 1,A _ 2,\ldots,A _ {i-1},A _ {i+1},A _ {i+2},\ldots,A _ N), and let the integer Y be A _ i.
  • Choose an integer j satisfying 1\le j\le i, and let the sequence (X _ 1,X _ 2,\ldots,X _ {j-1},Y,X _ j,X _ {j+1},\ldots,X _ {N-1}) of length N be the new A.

Note that in some cases the element can be inserted at the left end or the right end of the sequence.

Find the number of distinct sequences that can be obtained as a result of the operation.

Even if the pairs (i,j) chosen in the operation are different, the results are counted as the same if they are equal as sequences.

Constraints

• 1\le N\le2\times10 ^ 5
• 1\le A _ i\le N\ (1\le i\le N)
• All input values are integers.

Sample Input 1

6
1 4 1 4 2 1

Sample Output 1

12

For example, performing the operation with i=6,j=4 yields (1,4,1,1,4,2).

Besides this, the following 11 sequences can be obtained.

• (1,1,4,1,4,2)
• (1,1,4,4,2,1)
• (1,2,4,1,4,1)
• (1,4,1,2,4,1)
• (1,4,1,4,1,2)
• (1,4,1,4,2,1)
• (1,4,2,1,4,1)
• (1,4,4,1,2,1)
• (2,1,4,1,4,1)
• (4,1,1,4,2,1)
• (4,1,4,1,2,1)

Thus, print 12.

Sample Input 2

5
1 1 1 1 1

Sample Output 2

1

Note that sequences obtained by different pairs (i,j) are counted as one if they are equal as sequences.

Sample Input 3

30
24 22 18 20 14 22 14 14 26 14 26 26 20 22 24 18 22 22 14 24 18 14 14 24 22 18 18 26 14 20

Sample Output 3

303

Problem Statement

You are given a sequence A=(A_1,A_2,\dots,A_N) of length N. Find the number of (non-empty) contiguous subsequences whose sum is between L and R, inclusive.
Here, even if two contiguous subsequences are equal as sequences, they are counted separately if they are taken from different positions.

Constraints

• All input values are integers.
• 1 \le N \le 3 \times 10^5
• -10^{18} \le L \le R \le 10^{18}
• -10^{12} \le A_i \le 10^{12}

Sample Input 1

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

Sample Output 1

8

For this input, there are 8 pairs (l,r) such that the contiguous subsequence from the l-th through r-th elements satisfies the condition:

• (1,1),(1,2),(1,3),(1,5),(2,2),(2,5),(3,5),(4,4)

Sample Input 2

6 0 0
0 0 0 0 0 0

Sample Output 2

21

It is possible that L=R.

Sample Input 3

10 -126566 92319
11087 76694 -94782 -28589 -77903 -75549 31253 60353 -69062 -49587

Sample Output 3

34

Problem Statement

There is an integer sequence A=(A_1,A_2,\dots,A_N) of length N.
Process the following Q queries.

Type 1 :

1 i x

Change A_i to x.

Type 2 :

2 l r

Suppose that each -1 contained in A_l,A_{l+1},\dots,A_r can be replaced with an arbitrary positive integer. Print Yes if A_l,A_{l+1},\dots,A_r can all be made equal, and No otherwise.

Constraints

• All input values are integers.
• 1 \le N,Q \le 3 \times 10^5
• -1 \le A_i \le 10^6
• A_i \neq 0
• Queries of type 1 satisfy the following constraints:
  • 1 \le i \le N
  • -1 \le x \le 10^6
  • x \neq 0
• Queries of type 2 satisfy the following constraints:
  • 1 \le l \le r \le N

Sample Input 1

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

Sample Output 1

No
Yes
Yes
No
Yes

This input contains 9 queries.
Below, we explain the first 3 queries.

• Initially, A=(5,-1,3,-1,2,3,4,5).
• The 1-st query is of type 2, and the subarray in question is (3,-1,2,3). These cannot all be made equal by the operation in the problem statement, so print No.
• The 2-nd query is of type 1, and changes A_5 to -1. As a result, A=(5,-1,3,-1,-1,3,4,5).
• The 3-rd query is of type 2, and the subarray in question is (3,-1,-1,3). These can all be made equal by the operation in the problem statement, so print Yes.

Problem Statement

You are given strings S,X,Y consisting of 0, 1, and ?.

A string that can be obtained by the following procedure is called a good string.

• Choose a sequence t=(t _ 1,t _ 2,\ldots,t _ k) consisting of x and y such that there is no integer i\ (1\le i\lt k) with t _ i=t _ {i+1}=y.
• Let s=(s _ 1,s _ 2,\ldots,s _ k) be the sequence obtained by replacing each element of t with the string X if it is x, and with the string Y if it is y. Let T be the string obtained by concatenating s _ 1,s _ 2,\ldots,s _ k in this order.
• Replace each ? in T with 0 or 1 of your choice.

Find the number, modulo 998244353, of good strings that can be obtained by replacing each ? in S with 0 or 1.

Constraints

• S,X,Y are strings consisting of 0, 1, and ?.
• 1\le |S|\le2000 (Here, |S| denotes the length of S.)
• 1\le |X|\le8
• 1\le |Y|\le8

Sample Input 1

?0??11?1?
0?1
?1?

Sample Output 1

5

For example, the string 001111011, which can be obtained by replacing each ? in S with 0 or 1, is a good string. Starting the procedure with t=(x,y,x) gives T={}0?1?1?0?1. By replacing each ? in T with 0 or 1, we can obtain 001111011, so 001111011 is a good string.

Besides this, the four strings 001011010, 001011011, 001011110, 001011111 satisfy the condition. No other strings satisfy the condition, so print 5.

Sample Input 2

0?10?1?01?
???
?????

Sample Output 2

0

Note that y must not appear consecutively in t.

Sample Input 3

????????????1???1??0??????1???????1????????1????????????????0
?0??
?

Sample Output 3

992356689

Note that you should print the number of strings satisfying the condition modulo 998244353.