Problem Statement

In AtCoder, a user's rating is given as a positive integer, and based on this value, a certain number of ^ is displayed. Specifically, when the rating is between 1 and 399, inclusive, the display rules are as follows:

• When the rating is between 1 and 99, inclusive, ^ is displayed once.
• When the rating is between 100 and 199, inclusive, ^ is displayed twice.
• When the rating is between 200 and 299, inclusive, ^ is displayed three times.
• When the rating is between 300 and 399, inclusive, ^ is displayed four times.

Currently, Takahashi's rating is R. Here, it is guaranteed that R is an integer between 1 and 299, inclusive.
Find the minimum increase in rating required for him to increase the number of displayed ^.
It can be proved that under the constraints of this problem, he can increase the number of ^ without raising his rating to 400 or above.

Constraints

• 1 \leq R \leq 299
• R is an integer.

Sample Input 1

123

Sample Output 1

77

Takahashi's current rating is 123, and ^ is displayed twice.
By increasing his rating by 77, his rating will become 200, and ^ will be displayed three times. When the rating is 199 or below, ^ is displayed not more than twice, so print 77.

Sample Input 2

250

Sample Output 2

50

Problem Statement

There are N people, and the current hair length of the i-th person (1 \leq i \leq N) is L_i.
Each person's hair grows by 1 per day.

Print the number of days after which the number of people whose hair length is at least T becomes P or more for the first time.
If there are already P or more people whose hair length is at least T now, print 0.

Constraints

• 1 \leq N \leq 100
• 1 \leq L_i \leq 100
• 1 \leq T \leq 100
• 1 \leq P \leq N
• All input values are integers.

Sample Input 1

5 10 3
3 11 1 6 2

Sample Output 1

7

There are five people, and their current hair lengths are 3, 11, 1, 6, 2, so there is one person whose hair length is at least 10.

After seven days, the hair lengths of the people will be 10, 18, 8, 13, 9, respectively, and there will be three people whose hair length is at least 10.
After six days, there are only two people whose hair length is at least 10, not satisfying the condition, so print 7.

Sample Input 2

2 5 2
10 10

Sample Output 2

0

Since there are already two people whose hair length is at least 5 now, satisfying the condition, so print 0.

Sample Input 3

3 10 1
1 2 3

Sample Output 3

7

Problem Statement

You are given a string S of length N consisting only of lowercase English letters.

Find the number of strings obtained by permuting the characters of S (including the string S itself) that do not contain a palindrome of length K as a substring.

Here, a string T of length N is said to "contain a palindrome of length K as a substring" if and only if there exists a non-negative integer i not greater than (N-K) such that T_{i+j} = T_{i+K+1-j} for every integer j with 1 \leq j \leq K.
Here, T_k denotes the k-th character of the string T.

Constraints

• 2 \leq K \leq N \leq 10
• N and K are integers.
• S is a string of length N consisting only of lowercase English letters.

Sample Input 1

3 2
aab

Sample Output 1

1

The strings obtained by permuting aab are aab, aba, and baa. Among these, aab and baa contain the palindrome aa of length 2 as a substring.
Thus, the only string that satisfies the condition is aba, so print 1.

Sample Input 2

5 3
zzyyx

Sample Output 2

16

There are 30 strings obtained by permuting zzyyx, 16 of which do not contain a palindrome of length 3. Thus, print 16.

Sample Input 3

10 5
abcwxyzyxw

Sample Output 3

440640

Problem Statement

A non-negative integer X is called a palindrome number if its decimal representation (without leading zeros) is a palindrome.
For example, 363, 12344321, and 0 are all palindrome numbers.

Find the N-th smallest palindrome number.

Constraints

• 1 \leq N \leq 10^{18}
• N is an integer.

Sample Input 1

46

Sample Output 1

363

The 46th smallest palindrome number is 363.

Sample Input 2

1

Sample Output 2

0

Sample Input 3

1000000000000000000

Sample Output 3

90000000000000000000000000000000009

Problem Statement

There is an island of size H \times W, surrounded by the sea.
The island is divided into H rows and W columns of 1 \times 1 sections, and the elevation of the section at the i-th row from the top and the j-th column from the left (relative to the current sea level) is A_{i,j}.

Starting from now, the sea level rises by 1 each year.
Here, a section that is vertically or horizontally adjacent to the sea or a section sunk into the sea and has an elevation not greater than the sea level will sink into the sea.
Here, when a section newly sinks into the sea, any vertically or horizontally adjacent section with an elevation not greater than the sea level will also sink into the sea simultaneously, and this process repeats for the newly sunk sections.

For each i=1,2,\ldots, Y, find the area of the island that remains above sea level i years from now.

Constraints

• 1 \leq H, W \leq 1000
• 1 \leq Y \leq 10^5
• 1 \leq A_{i,j} \leq 10^5
• All input values are integers.

Sample Input 1

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

Sample Output 1

9
7
6
5
4

Let (i,j) denote the section at the i-th row from the top and the j-th column from the left. Then, the following happens:

• After 1 year, the sea level is higher than now by 1, but there are no sections with an elevation of 1 that are adjacent to the sea, so no sections sink. Thus, the first line should contain 9.
• After 2 years, the sea level is higher than now by 2, and (1,2) sinks into the sea. This makes (2,2) adjacent to a sunken section, and its elevation is not greater than 2, so it also sinks. No other sections sink at this point. Thus, two sections sink, and the second line should contain 9-2=7.
• After 3 years, the sea level is higher than now by 3, and (2,1) sinks into the sea. No other sections sink. Thus, the third line should contain 6.
• After 4 years, the sea level is higher than now by 4, and (2,3) sinks into the sea. No other sections sink. Thus, the fourth line should contain 5.
• After 5 years, the sea level is higher than now by 5, and (3,2) sinks into the sea. No other sections sink. Thus, the fifth line should contain 4.

Therefore, print 9, 7, 6, 5, 4 in this order, each on a new line.

Sample Input 2

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

Sample Output 2

15
7
0

Problem Statement

You are given an integer N. Print a string S that satisfies all of the following conditions. If no such string exists, print -1.

• S is a string of length between 1 and 1000, inclusive, consisting of the characters 1, 2, 3, 4, 5, 6, 7, 8, 9, and * (multiplication symbol).
• S is a palindrome.
• The first character of S is a digit.
• The value of S when evaluated as a formula equals N.

Constraints

• 1 \leq N \leq 10^{12}
• N is an integer.

Sample Input 1

363

Sample Output 1

11*3*11

S = 11*3*11 satisfies the conditions in the problem statement. Another string that satisfies the conditions is S= 363.

Sample Input 2

101

Sample Output 2

-1

Note that S must not contain the digit 0.

Sample Input 3

3154625100

Sample Output 3

2*57*184481*75*2

Problem Statement

You are given two sequences of length N: D=(D_1, D_2, \dots, D_N) and P=(P_1, P_2, \dots, P_N).

Process Q queries in the order they are given. Each query is given in the following format:

• c x y: Change D_c to x and P_c to y. Then, solve the following problem and print the answer.

There are N jobs numbered 1 to N.
Starting from today (consider this as day 1), you will choose and complete one job per day for N days.
If you complete job i on or before day D_i, you will receive a reward of P_i. (If you do not complete it by day D_i, you get nothing.)
Find the maximum total reward you can achieve by choosing the optimal order of completing the jobs.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq Q \leq 10^5
• 1 \leq D_i \leq N
• 1 \leq P_i \leq 10^9
• 1 \leq c \leq N
• 1 \leq x \leq N
• 1 \leq y \leq 10^9
• All input values are integers.

Sample Input 1

3 2
1 2 3
3 6 3
3 1 4
2 3 9

Sample Output 1

10
13

The first query is as follows:

• Update D_3 to 1 and P_3 to 4. Now, D = (1, 2, 1) and P = (3, 6, 4).
• In the subproblem, one optimal procedure is to complete job 3 on day 1, job 2 on day 2, and job 1 on day 3. The total reward is 10, so print 10.

The second query is as follows:

• Update D_2 to 3 and P_2 to 9. Now, D = (1, 3, 1) and P = (3, 9, 4).
• In the subproblem, one optimal procedure is to complete job 3 on day 1, job 1 on day 2, and job 2 on day 3. The total reward is 13, so print 13.

Sample Input 2

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

Sample Output 2

5000000000

Sample Input 3

10 10
6 2 4 1 5 1 6 6 5 3
45 65 71 52 86 52 48 60 40 98
5 6 5
8 4 34
6 7 83
1 3 21
7 5 85
7 4 51
8 2 81
2 7 54
6 1 5
8 6 30

Sample Output 3

394
379
462
457
459
414
443
479
401
396