Problem Statement

You are given an integer N and a string S consisting of lowercase English letters with length less than N.

Print the string obtained by repeatedly adding the lowercase English letter o to the beginning of S until its length becomes N.

Constraints

• 2\leq N \leq 100
• N is an integer.
• S is a string consisting of lowercase English letters with length between 1 and N - 1, inclusive.

Sample Input 1

5
abc

Sample Output 1

ooabc

Since N=5 and the length of S is 3, the answer is the string obtained by adding 5-3=2 os to the beginning of S.

Sample Input 2

2
o

Sample Output 2

oo

Sample Input 3

12
vgxgpuam

Sample Output 3

oooovgxgpuam

Problem Statement

You are given two integers A and B, each between 0 and 9, inclusive.

Print any integer between 0 and 9, inclusive, that is not equal to A + B.

Constraints

• 0 \leq A \leq 9
• 0 \leq B \leq 9
• A + B \leq 9
• A and B are integers.

Sample Input 1

2 5

Sample Output 1

2

When A = 2, B = 5, we have A + B = 7. Thus, printing any of 0, 1, 2, 3, 4, 5, 6, 8, 9 is correct.

Sample Input 2

0 0

Sample Output 2

9

Sample Input 3

7 1

Sample Output 3

4

Problem Statement

Tiles are aligned in N horizontal rows and N vertical columns. Each tile has a grid with A horizontal rows and B vertical columns. On the whole, the tiles form a grid X with (A\times N) horizontal rows and (B\times N) vertical columns.
For 1\leq i,j \leq N, Tile (i,j) denotes the tile at the i-th row from the top and the j-th column from the left.

Each square of X is painted as follows.

• Each tile is either a white tile or a black tile.
• Every square in a white tile is painted white; every square in a black tile is painted black.
• Tile (1,1) is a white tile.
• Two tiles sharing a side have different colors. Here, Tile (a,b) and Tile (c,d) are said to be sharing a side if and only if |a-c|+|b-d|=1 (where |x| denotes the absolute value of x).

Print the grid X in the format specified in the Output section.

Constraints

• 1 \leq N,A,B \leq 10
• All values in input are integers.

Sample Input 1

4 3 2

Sample Output 1

..##..##
..##..##
..##..##
##..##..
##..##..
##..##..
..##..##
..##..##
..##..##
##..##..
##..##..
##..##..

Sample Input 2

5 1 5

Sample Output 2

.....#####.....#####.....
#####.....#####.....#####
.....#####.....#####.....
#####.....#####.....#####
.....#####.....#####.....

Sample Input 3

4 4 1

Sample Output 3

.#.#
.#.#
.#.#
.#.#
#.#.
#.#.
#.#.
#.#.
.#.#
.#.#
.#.#
.#.#
#.#.
#.#.
#.#.
#.#.

Sample Input 4

1 4 4

Sample Output 4

....
....
....
....

Problem Statement

You are given a string T consisting of lowercase English letters and ?, and a string U consisting of lowercase English letters.

The string T is obtained by taking some lowercase-only string S and replacing exactly four of its characters with ?.

Determine whether it is possible that the original string S contained U as a contiguous substring.

Constraints

• T is a string of length between 4 and 10, inclusive, consisting of lowercase letters and ?.
• T contains exactly four occurrences of ?.
• U is a string of length between 1 and |T|, inclusive, consisting of lowercase letters.

Sample Input 1

tak??a?h?
nashi

Sample Output 1

Yes

For example, if S is takanashi, it contains nashi as a contiguous substring.

Sample Input 2

??e??e
snuke

Sample Output 2

No

No matter what characters replace the ?s in T, S cannot contain snuke as a contiguous substring.

Sample Input 3

????
aoki

Sample Output 3

Yes

Problem Statement

There are N people, each of whom is either a child or an adult. The i-th person has a weight of W_i.
Whether each person is a child or an adult is specified by a string S of length N consisting of 0 and 1.
If the i-th character of S is 0, then the i-th person is a child; if it is 1, then the i-th person is an adult.

When Takahashi the robot is given a real number X, Takahashi judges a person with a weight less than X to be a child and a person with a weight more than or equal to X to be an adult.
For a real value X, let f(X) be the number of people whom Takahashi correctly judges whether they are children or adults.

Find the maximum value of f(X) for all real values of X.

Constraints

• 1\leq N\leq 2\times 10^5
• S is a string of length N consisting of 0 and 1.
• 1\leq W_i\leq 10^9
• N and W_i are integers.

Sample Input 1

5
10101
60 45 30 40 80

Sample Output 1

4

When Takahashi is given X=50, it judges the 2-nd, 3-rd, and 4-th people to be children and the 1-st and 5-th to be adults.
In reality, the 2-nd and 4-th are children, and the 1-st, 3-rd, and 5-th are adults, so the 1-st, 2-nd, 4-th, and 5-th people are correctly judged. Thus, f(50)=4.

This is the maximum since there is no X that judges correctly for all 5 people. Thus, 4 should be printed.

Sample Input 2

3
000
1 2 3

Sample Output 2

3

For example, X=10 achieves the maximum value f(10)=3.
Note that the people may be all children or all adults.

Sample Input 3

5
10101
60 50 50 50 60

Sample Output 3

4

For example, X=55 achieves the maximum value f(55)=4.
Note that there may be multiple people with the same weight.

Problem Statement

Takahashi is managing the number of trees in his garden. Initially, there are no trees in the garden.

Q queries are given in order. Each query is one of the following two types. Immediately after processing each query, output the number of trees currently in the garden.

• 1 h : Add one new tree of height h to the garden.
• 2 h : Remove all trees currently in the garden whose height is at most h.

Constraints

• 1 \le Q \le 3 \times 10^5
• 1 \le h \le 10^9
• All input values are integers.

Sample Input 1

5
1 5
1 7
1 8
2 7
1 3

Sample Output 1

1
2
3
1
2

The number of trees changes as follows.

• A tree of height 5 is added. The garden contains one tree of height 5.
• A tree of height 7 is added. The garden contains two trees of heights 5, 7.
• A tree of height 8 is added. The garden contains three trees of heights 5, 7, 8.
• Trees of height at most 7 are removed. The garden contains one tree of height 8.
• A tree of height 3 is added. The garden contains two trees of heights 8, 3.

Sample Input 2

12
2 256601193
1 85138616
1 202564041
2 276477192
1 55551662
1 170271057
2 754166580
1 854388209
1 772036624
2 651124113
1 301137866
2 290875185

Sample Output 2

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

Problem Statement

There is a directed graph (not necessarily simple) with N vertices and M edges, where the vertices are numbered as vertices 1, 2, \ldots, N.
The i-th (1\leq i\leq M) edge goes from vertex U_i to vertex V_i with cost C_i. Additionally, the out-degree of each vertex is at most 4.

Find all vertices v (1\leq v\leq N) that satisfy the following condition:

There exists a path from vertex 1 to vertex v that satisfies both of the following conditions:

• It traverses exactly L edges. If the same edge is traversed multiple times, each traversal is counted.
• The sum of the costs of the traversed edges is at least S and at most T. (If the same edge is traversed multiple times, the cost is added to the sum each time.)

Constraints

• 1\leq N\leq 2\times 10^5
• 1\leq M\leq 2\times 10^5
• 1\leq L \leq 10
• 1\leq S\leq T \leq 10^9
• 1\leq U_i,V_i\leq N
• 1\leq C_i\leq 10^8
• The out-degree of each vertex is at most 4.
• All input values are integers.

Sample Input 1

5 8 3 80 100
1 2 20
1 3 70
2 1 30
2 5 10
3 2 10
3 4 30
3 5 20
5 1 70

Sample Output 1

1 5

The given graph is as shown in the left figure below. The cost of each edge is shown near the starting vertex of that edge.

Here, the following holds:

• For the path from vertex 1 to vertex 1, consider vertex 1 \to vertex 2 \to vertex 5 \to vertex 1 (center of the figure above). This traverses exactly three edges, and the sum of the costs of the traversed edges is 20+10+70=100, so it satisfies the condition.
• There is no path from vertex 1 to vertex 2 that satisfies the condition. One path that traverses exactly three edges is vertex 1 \to vertex 2 \to vertex 1 \to vertex 2, but the sum of the costs of the edges traversed in this path is 20+30+20=70, which is less than 80, so it does not satisfy the condition.
• There is no path from vertex 1 to vertex 3 that satisfies the condition. One path that traverses exactly three edges is vertex 1 \to vertex 2 \to vertex 1 \to vertex 3, but the sum of the costs of the edges traversed in this path is 20+30+70=120, which is greater than 100, so it does not satisfy the condition.
• There is no path from vertex 1 to vertex 4 that satisfies the condition.
• For the path from vertex 1 to vertex 5, consider vertex 1 \to vertex 3 \to vertex 2 \to vertex 5 (right of the figure above). This traverses exactly three edges, and the sum of the costs of the traversed edges is 70+10+10=90, so it satisfies the condition.

Therefore, print 1, 5 in this order. Note that you need to print those vertices that satisfy the condition in ascending order.

Sample Input 2

10 1 1 1 100
2 3 1

Sample Output 2

If there are no vertices that satisfy the condition, print an empty line.

Sample Input 3

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

Sample Output 3

1 2

The graph may contain self-loops and multiple edges.
In this test case, the out-degrees from vertices 1 and 2 are 4 and 1, respectively.

Problem Statement

Let us call a positive integer n that satisfies the following condition an arithmetic number.

• Let d_i be the i-th digit of n from the top (when n is written in base 10 without unnecessary leading zeros.) Then, (d_2-d_1)=(d_3-d_2)=\dots=(d_k-d_{k-1}) holds, where k is the number of digits in n.
  • This condition can be rephrased into the sequence (d_1,d_2,\dots,d_k) being arithmetic.
  • If n is a 1-digit integer, it is assumed to be an arithmetic number.

For example, 234,369,86420,17,95,8,11,777 are arithmetic numbers, while 751,919,2022,246810,2356 are not.

Find the smallest arithmetic number not less than X.

Constraints

• X is an integer between 1 and 10^{17} (inclusive).

Sample Input 1

152

Sample Output 1

159

The smallest arithmetic number not less than 152 is 159.

Sample Input 2

88

Sample Output 2

88

X itself may be an arithmetic number.

Sample Input 3

8989898989

Sample Output 3

9876543210

Problem Statement

There is a sequence A of N non-negative integers, all initially 0. Process Q queries given in order.
For the q-th query, you are given integers l_q, r_q satisfying 1 \leq l_q \leq r_q \leq N and a positive integer a_q. Perform the following in order:

• Add a_q to each of A_{l_q}, A_{{l_q}+1}, \dots, A_{r_q}.
• Then, letting M=r_q-l_q+1 and B=(B_1,B_2,\dots,B_M)=(A_{l_q}, A_{l_q+1}, \dots, A_{r_q}), find the answer to the following problem:

There are M slimes 1,2,\dots,M, where the m-th slime has weight B_m.
Repeat the operation of choosing two slimes and merging them M-1 times.
When slimes of weights x and y are merged, a slime of weight x+y appears and the original two slimes disappear. This incurs a cost of x \times y.
Find, modulo 998244353, the minimum possible total cost of the M-1 operations.

Note that the changes made on A in each query carry over to subsequent queries.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq Q \leq 10^5
• 1 \leq l_q \leq r_q \leq N
• 1 \leq a_q \leq 10^9
• All input values are integers.

Sample Input 1

5 4
1 3 22
3 4 13
5 5 455
1 5 1000000000

Sample Output 1

1452
455
0
21421644

After the first query, A=(22,22,22,0,0) and B=(22,22,22). Merging the first and third slimes first incurs a cost of 22 \times 22=484. Then merging the remaining two slimes incurs a cost of 22 \times 44=968. The total cost is 484+968=1452. Moreover, the total cost cannot be made smaller than this.
After the second query, A=(22,22,35,13,0) and B=(35,13). The answer is 35 \times 13 = 455.