Problem Statement

We have N cups of ice cream.
The flavor and deliciousness of the i-th cup are F_i and S_i, respectively (S_i is an even number).

You will choose and eat two of the N cups.
Your satisfaction here is defined as follows.

• Let s and t (s \ge t) be the deliciousness of the eaten cups.
  • If the two cups have different flavors, your satisfaction is \displaystyle s+t.
  • Otherwise, your satisfaction is \displaystyle s + \frac{t}{2}.

Find the maximum achievable satisfaction.

Constraints

• All input values are integers.
• 2 \le N \le 3 \times 10^5
• 1 \le F_i \le N
• 2 \le S_i \le 10^9
• S_i is even.

Sample Input 1

4
1 4
2 10
2 8
3 6

Sample Output 1

16

Consider eating the second and fourth cups.

• The second cup has a flavor of 2 and deliciousness of 10.
• The fourth cup has a flavor of 3 and deliciousness of 6.
• Since they have different flavors, your satisfaction is 10+6=16.

Thus, you can achieve the satisfaction of 16.
You cannot achieve a satisfaction greater than 16.

Sample Input 2

4
4 10
3 2
2 4
4 12

Sample Output 2

17

Consider eating the first and fourth cups.

• The first cup has a flavor of 4 and deliciousness of 10.
• The fourth cup has a flavor of 4 and deliciousness of 12.
• Since they have the same flavor, your satisfaction is 12+\frac{10}{2}=17.

Thus, you can achieve the satisfaction of 17.
You cannot achieve a satisfaction greater than 17.

Problem Statement

Planning to place many PCs in his room, Takahashi has decided to write a code that finds how many PCs he can place in his room.

You are given H strings S_1,S_2,\ldots,S_H, each of length W, consisting of . and T.

Takahashi may perform the following operation any number of times (possibly zero):

• Choose integers satisfying 1\leq i \leq H and 1 \leq j \leq W-1 such that the j-th and (j+1)-th characters of S_i are both T. Replace the j-th character of S_i with P, and (j+1)-th with C.

He tries to maximize the number of times he performs the operation. Find possible resulting S_1,S_2,\ldots,S_H.

Constraints

• 1\leq H \leq 100
• 2\leq W \leq 100
• H and W are integers.
• S_i is a string of length W consisting of . and T.

Sample Input 1

2 3
TTT
T.T

Sample Output 1

PCT
T.T

He can perform the operation at most once.

For example, an operation with (i,j)=(1,1) makes S_1 PCT.

Sample Input 2

3 5
TTT..
.TTT.
TTTTT

Sample Output 2

PCT..
.PCT.
PCTPC

Problem Statement

There is a sequence A = (A_0, A_1, \dots, A_{N - 1}) with N = 2^{20} terms. Initially, every term is -1.

Process Q queries in order. The i-th query (1 \leq i \leq Q) is described by an integer t_i such that t_i = 1 or t_i = 2, and another integer x_i, as follows.

• If t_i = 1, do the following in order.
  1. Define an integer h as h = x_i.
  2. While A_{h \bmod N} \neq -1, keep adding 1 to h. We can prove that this process ends after finite iterations under the Constraints of this problem.
  3. Replace the value of A_{h \bmod N} with x_i.
• If t_i = 2, print the value of A_{x_i \bmod N} at that time.

Here, for integers a and b, a \bmod b denotes the remainder when a is divided by b.

Constraints

• 1 \leq Q \leq 2 \times 10^5
• t_i \in \{ 1, 2 \} \, (1 \leq i \leq Q)
• 0 \leq x_i \leq 10^{18} \, (1 \leq i \leq Q)
• There is at least one i (1 \leq i \leq Q) such that t_i = 2.
• All values in input are integers.

Sample Input 1

4
1 1048577
1 1
2 2097153
2 3

Sample Output 1

1048577
-1

We have x_1 \bmod N = 1, so the first query sets A_1 = 1048577.

In the second query, initially we have h = x_2, for which A_{h \bmod N} = A_{1} \neq -1, so we add 1 to h. Now we have A_{h \bmod N} = A_{2} = -1, so this query sets A_2 = 1.

In the third query, we print A_{x_3 \bmod N} = A_{1} = 1048577.

In the fourth query, we print A_{x_4 \bmod N} = A_{3} = -1.

Note that, in this problem, N = 2^{20} = 1048576 is a constant and not given in input.

Problem Statement

The digit sum of a positive integer n is defined as the sum of its digits when n is written in decimal. For example, the digit sum of 2025 is 2 + 0 + 2 + 5 = 9.
A positive integer n is called a good integer if it is divisible by its digit sum. For example, 2025 is a good integer because it is divisible by its digit sum of 9.
A pair of positive integers (a, a+1) is called twin good integers if both a and a+1 are good integers. For example, (2024, 2025) is twin good integers.

You are given a positive integer N. Find a pair of twin good integers (a, a + 1) such that N \leq a and a + 1 \leq 2N. If no such pair exists, report that fact.

Constraints

• N is an integer at least 1 and less than 10^{100000}.

Sample Input 1

5

Sample Output 1

8

(8, 9) is a valid pair of twin good integers satisfying the conditions. Other examples include (5, 6), (6, 7), (7, 8), (9, 10).

Sample Input 2

21

Sample Output 2

-1

No pair of twin good integers satisfies the conditions.

Sample Input 3

1234

Sample Output 3

2024

(2024, 2025) is a valid pair of twin good integers.

Sample Input 4

1234567890123456789012345678901234567890

Sample Output 4

1548651852734633803438094164372911259190

Problem Statement

For a permutation P = (p_1, p_2, \dots, p_N) of (1,2, \dots, N), let us define the score S(P) of P as follows.

• There are N people, numbered 1,2,\dots,N. Additionally, Snuke is there. Initially, Person i (1 \leq i \leq N) has Ball i.
  Each time Snuke screams, every Person i such that i \neq p_i gives their ball to Person p_i simultaneously.
  If, after screaming at least once, every Person i has Ball i, Snuke stops screaming.
  The score is the number of times Snuke screams until he stops. Here, it is guaranteed that the score will be a finite value.

There are N! permutations P of (1,2, \dots, N). Find the sum, modulo 998244353, of the scores of those permutations, each raised to the K-th power.

• Formally, let S_N be the set of the permutations of (1,2, \dots, N). Compute the following: \displaystyle \left(\sum_{P \in S_N} S(P)^K \right) \bmod {998244353}.

Constraints

• 2 \leq N \leq 50
• 1 \leq K \leq 10^4
• All values in input are integers.

Sample Input 1

2 2

Sample Output 1

5

When N = 2, there are two possible permutations P: (1,2),(2,1).

The score of the permutation (1,2) is found as follows.

• Initially, Person 1 has Ball 1, and Person 2 has Ball 2.
  After Snuke's first scream, Person 1 has Ball 1, and Person 2 has Ball 2.
  Here, every Person i has Ball i, so he stops screaming.
  Thus, the score is 1.

The score of the permutation (2,1) is found as follows.

• Initially, Person 1 has Ball 1, and Person 2 has Ball 2.
  After Snuke's first scream, Person 1 has Ball 2, and Person 2 has Ball 1.
  After Snuke's second scream, Person 1 has Ball 1, and Person 2 has Ball 2.
  Here, every Person i has Ball i, so he stops screaming.
  Thus, the score is 2.

Therefore, the answer in this case is 1^2 + 2^2 = 5.

Sample Input 2

3 3

Sample Output 2

79

All permutations and their scores are listed below.

• (1,2,3): The score is 1.
• (1,3,2): The score is 2.
• (2,1,3): The score is 2.
• (2,3,1): The score is 3.
• (3,1,2): The score is 3.
• (3,2,1): The score is 2.

Thus, we should print 1^3 + 2^3 + 2^3 + 3^3 + 3^3 + 2^3 = 79.

Sample Input 3

50 10000

Sample Output 3

77436607