Problem Statement

1 foot is 12 inches.

How many inches is A feet B inches?

Constraints

• 1 \leq A \leq 8
• 0 \leq B \leq 11
• All input values are integers.

Sample Input 1

6 7

Sample Output 1

79

6 feet 7 inches is 6 \times 12 + 7 = 79 inches.

Sample Input 2

4 11

Sample Output 2

59

4 feet 11 inches is 4 \times 12 + 11 = 59 inches.

Sample Input 3

8 0

Sample Output 3

96

8 feet 0 inches is 8 \times 12 + 0 = 96 inches.

Problem Statement

AtCoder Inc. sells merchandise through its online shop.

Takahashi has decided to purchase N types of products from there.
For each integer i from 1 to N, the i-th type of product has a price of P_i yen each, and he will buy Q_i of this.

Additionally, he must pay a shipping fee.
The shipping fee is 0 yen if the total price of the products purchased is S yen or above, and K yen otherwise.

He will pay the total price of the products purchased plus the shipping fee.
Calculate the amount he will pay.

Constraints

• 1\leq N\leq 100
• 1\leq S\leq 10000
• 1\leq K\leq 10000
• 1\leq P_i\leq 10000
• 1\leq Q_i\leq 100
• All input values are integers.

Sample Input 1

2 2000 500
1000 1
100 6

Sample Output 1

2100

Takahashi buys one product for 1000 yen and six products for 100 yen each.
Thus, the total price of the products is 1000\times 1+100\times 6=1600 yen.
Since the total amount for the products is less than 2000 yen, the shipping fee will be 500 yen.
Therefore, the amount Takahashi will pay is 1600+500=2100 yen.

Sample Input 2

3 2000 500
1000 1
100 6
5000 1

Sample Output 2

6600

The total price of the products is 1000\times 1+100\times 6+5000\times 1=6600 yen.
Since the total amount for the products is not less than 2000 yen, the shipping fee will be 0 yen.
Therefore, the amount Takahashi will pay is 6600+0=6600 yen.

Sample Input 3

2 2000 500
1000 1
1000 1

Sample Output 3

2000

There may be multiple products with the same price per item.

Problem Statement

You are given N strings, each of length 2, consisting of uppercase English letters and digits. The i-th string is S_i.
Determine whether the following three conditions are all satisfied.
・For every string, the first character is one of H, D, C, and S.
・For every string, the second character is one of A, 2, 3, 4, 5, 6, 7, 8, 9, T, J, Q, K.
・All strings are pairwise different. That is, if i \neq j, then S_i \neq S_j.

Constraints

• 1 \leq N \leq 52
• S_i is a string of length 2 consisting of uppercase English letters and digits.

Sample Input 1

4
H3
DA
D3
SK

Sample Output 1

Yes

One can verify that the three conditions are all satisfied.

Sample Input 2

5
H3
DA
CK
H3
S7

Sample Output 2

No

Both S_1 and S_4 are H3, violating the third condition.

Sample Input 3

4
3H
AD
3D
KS

Sample Output 3

No

Sample Input 4

5
00
AA
XX
YY
ZZ

Sample Output 4

No

Problem Statement

There are N cities numbered 1, \dots, N, and M roads connecting cities.
The i-th road (1 \leq i \leq M) connects city A_i and city B_i.

Print N lines as follows.

• Let d_i be the number of cities directly connected to city i \, (1 \leq i \leq N), and those cities be city a_{i, 1}, \dots, city a_{i, d_i}, in ascending order.
• The i-th line (1 \leq i \leq N) should contain d_i + 1 integers d_i, a_{i, 1}, \dots, a_{i, d_i} in this order, separated by spaces.

Constraints

• 2 \leq N \leq 10^5
• 1 \leq M \leq 10^5
• 1 \leq A_i \lt B_i \leq N \, (1 \leq i \leq M)
• (A_i, B_i) \neq (A_j, B_j) if (i \neq j).
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

3 2 3 6
2 1 5
2 1 6
0
2 2 6
3 1 3 5

The cities directly connected to city 1 are city 2, city 3, and city 6. Thus, we have d_1 = 3, a_{1, 1} = 2, a_{1, 2} = 3, a_{1, 3} = 6, so you should print 3, 2, 3, 6 in the first line in this order, separated by spaces.

Note that a_{i, 1}, \dots, a_{i, d_i} must be in ascending order. For instance, it is unacceptable to print 3, 3, 2, 6 in the first line in this order.

Sample Input 2

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

Sample Output 2

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

Problem Statement

You are given a positive integer N and an integer sequence A = (A_1,A_2,\dots,A_N) of length N.

Determine whether there exists a non-empty (contiguous) subarray of A that has a repeated value, occurring multiple times in A. If such a subarray exists, find the length of the shortest such subarray.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq 10^6 \ (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

5
3 9 5 3 1

Sample Output 1

4

(3,9,5,3) and (3,9,5,3,1) satisfy the condition. The shorter one is (3,9,5,3), which has length 4.

Sample Input 2

4
2 5 3 1

Sample Output 2

-1

There is no subarray that satisfies the condition.

Sample Input 3

10
1 1 2 3 5 8 13 21 34 55

Sample Output 3

2

Problem Statement

There are N people participating in an event, and the transportation cost for the i-th person is A_i yen.

Takahashi, the organizer of the event, decided to set a maximum limit x for the transportation subsidy. The subsidy for person i will be \min(x, A_i) yen. Here, x must be a non-negative integer.

Given that Takahashi's budget is M yen, and he wants the total transportation subsidy for all N people to be at most M yen, what is the maximum possible value of the subsidy limit x?

If the subsidy limit can be made infinitely large, report that instead.

Constraints

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

Sample Input 1

4 8
1 3 2 4

Sample Output 1

2

If the subsidy limit is set to 2 yen, the total transportation subsidy for all N people is \min(2,1) + \min(2,3) + \min(2,2) + \min(2,4) = 7 yen, which is within the budget of 8 yen.

If the subsidy limit is set to 3 yen, the total transportation subsidy for all N people is \min(3,1) + \min(3,3) + \min(3,2) + \min(3,4) = 9 yen, which exceeds the budget of 8 yen.

Therefore, the maximum possible value of the subsidy limit is 2 yen.

Sample Input 2

3 20
5 3 2

Sample Output 2

infinite

The subsidy limit can be made infinitely large.

Sample Input 3

10 23
2 5 6 5 2 1 7 9 7 2

Sample Output 3

2

Problem Statement

Let N be a positive integer. Define the imbalance of a sequence A=(A_1, A_2, \dots, A_{2^N}) of non-negative integers of length 2^N as the non-negative integer value obtained by the following operation:

• Initially, set X=0.
• Perform the following series of operations N times:
  • Update X to \max(X, \max(A) - \min(A)), where \max(A) and \min(A) denote the maximum and minimum values of sequence A, respectively.
  • Form a new sequence of half the length by pairing elements from the beginning two by two and arranging their sums. That is, set A \gets (A_1 + A_2, A_3 + A_4, \dots, A_{\vert A \vert - 1} + A_{\vert A \vert}).
• The final value of X is the imbalance.

For example, when N=2, A=(6, 8, 3, 5), the imbalance is 6 through the following steps:

• Initially, X=0.
• The first series of operations is as follows:
  • Update X to \max(X, \max(A) - \min(A)) = \max(0, 8 - 3) = 5.
  • Set A to (6+8, 3+5) = (14, 8).
• The second series of operations is as follows:
  • Update X to \max(X, \max(A) - \min(A)) = \max(5, 14 - 8) = 6.
  • Set A to (14 + 8) = (22).
• Finally, X=6.

You are given a non-negative integer K. Among all sequences of non-negative integers of length 2^N with sum K, construct a sequence that minimizes the imbalance.

Constraints

• 1 \leq N \leq 20
• 0 \leq K \leq 10^9
• N and K are integers.

Sample Input 1

1 11

Sample Output 1

1
5 6

(5, 6) is a sequence with imbalance 1, which is the minimum imbalance among sequences satisfying the condition.

Sample Input 2

3 56

Sample Output 2

0
7 7 7 7 7 7 7 7

Problem Statement

You are given a sequence of positive integers of length N: A=(A_1,A_2,\ldots,A_N). Find the number of triples of positive integers (i,j,k) that satisfy all of the following conditions:

• 1\leq i < j < k\leq N,
• A_i = A_k,
• A_i \neq A_j.

Constraints

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

Sample Input 1

5
1 2 1 3 2

Sample Output 1

3

The following three triples of positive integers (i,j,k) satisfy the conditions:

• (i,j,k)=(1,2,3)
• (i,j,k)=(2,3,5)
• (i,j,k)=(2,4,5)

Sample Input 2

7
1 2 3 4 5 6 7

Sample Output 2

0

There may be no triples of positive integers (i,j,k) that satisfy the conditions.

Sample Input 3

13
9 7 11 7 3 8 1 13 11 11 11 6 13

Sample Output 3

20

Problem Statement

A DDoS-type string is a string of length 4 consisting of uppercase and lowercase English letters satisfying both of the following conditions.

• The first, second, and fourth characters are uppercase English letters, and the third character is a lowercase English letter.
• The first and second characters are equal.

For instance, DDoS and AAaA are DDoS-type strings, while neither ddos nor IPoE is.

You are given a string S consisting of uppercase and lowercase English letters and ?. Let q be the number of occurrences of ? in S. There are 52^q strings that can be obtained by independently replacing each ? in S with an uppercase or lowercase English letter. Among these strings, find the number of ones that do not contain a DDoS-type string as a subsequence, modulo 998244353.

Notes

A subsequence of a string is a string obtained by removing zero or more characters from the string and concatenating the remaining characters without changing the order.
For instance, AC is a subsequence of ABC, while RE is not a subsequence of ECR.

Constraints

• S consists of uppercase English letters, lowercase English letters, and ?.
• The length of S is between 4 and 3\times 10^5, inclusive.

Sample Input 1

DD??S

Sample Output 1

676

When at least one of the ?s is replaced with a lowercase English letter, the resulting string will contain a DDoS-type string as a subsequence.

Sample Input 2

????????????????????????????????????????

Sample Output 2

858572093

Find the count modulo 998244353.

Sample Input 3

?D??S

Sample Output 3

136604