Problem Statement

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

Output the string obtained by inserting o between each pair of adjacent characters of S.

Constraints

• S is a string of length between 2 and 10 (inclusive) consisting of lowercase English letters.

Sample Input 1

mtr

Sample Output 1

motor

Sample Input 2

mnclr

Sample Output 2

monocolor

Sample Input 3

oo

Sample Output 3

ooo

Problem Statement

In the Kingdom of AtCoder, three kinds of coins — 1-yen coins, 10-yen coins, and 100-yen coins — and 1000-yen bills are in circulation.

Takahashi made N purchases, starting from a state where he had 10^{100} 1000-yen bills and 0 coins.

In the i-th purchase, he bought an item worth A_i yen.
For the payment, he paid using only the minimum number of 1000-yen bills such that the total amount paid was at least A_i yen, and received the change so that the total number of coins received as change was minimized.

Find the number of each type of coin that Takahashi has at the point when all N purchases are finished.

Constraints

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

Sample Input 1

3
1296 110 1

Sample Output 1

13 18 24

In the first purchase, for the payment of 1296 yen, Takahashi pays with two 1000-yen bills, and receives seven 100-yen coins and four 1-yen coins as change.

In the second purchase, for the payment of 110 yen, he pays with one 1000-yen bill, and receives eight 100-yen coins and nine 10-yen coins as change.

In the third purchase, for the payment of 1 yen, he pays with one 1000-yen bill, and receives nine 100-yen coins, nine 10-yen coins, and nine 1-yen coins as change.

At the point when the three purchases are finished, he has 13 1-yen coins, 18 10-yen coins, and 24 100-yen coins.

Sample Input 2

12
3141 592 65358 9 79 323 84 6264 3 38327 950 28

Sample Output 2

52 59 82

Problem Statement

There are N towns arranged in a line. The towns are numbered 1, 2, \ldots, N, and for each integer i satisfying 1 \leq i \leq N-1, town i and town i + 1 are connected by a road of length A_i.

You are initially at town S. You can repeatedly move between two towns connected by a road using that road.

Find the maximum possible number of towns visited in a sequence of moves such that the total distance traveled is at most L. Here, town S is included among the towns visited, and a town visited multiple times is counted only once.

Constraints

• 2 \leq N \leq 8000
• 1 \leq S \leq N
• 0 \leq L \leq 10^{18}
• 1 \leq A_i \leq 10^9
• All input values are integers.

Sample Input 1

6 3 10
5 2 4 1 6

Sample Output 1

4

You are initially at town 3. If you move in the order town 3 \to 2 \to 3 \to 4 \to 5, the total distance traveled is 2 + 2 + 4 + 1 = 9, and the towns visited are 2, 3, 4, 5, that is, four towns.

It is impossible to visit five or more towns with a total travel distance of at most 10, so the answer for this case is 4.

Sample Input 2

8 8 17
2 3 4 4 3 5 1

Sample Output 2

6

Sample Input 3

2 1 1000000000000000000
10000

Sample Output 3

2

Sample Input 4

9 6 28
5 4 9 2 3 6 1 4

Sample Output 4

6

Problem Statement

You are given a string S consisting of lowercase English letters. If there exists a prime number P satisfying the following condition, find one such P.

Condition: Let T be the string representing P in decimal notation without an extra leading 0. Then, |S|=|T|, and for every 1\leq i< j \leq |S|, we have S_i=S_j if and only if T_i=T_j.

Constraints

• S is a string of length between 1 and 7 (inclusive) consisting of lowercase English letters.

Sample Input 1

motor

Sample Output 1

10607

Besides this, for example, outputting 40709 would also be accepted. However, for example, 81817 does not satisfy the condition, so it would not be accepted.

Sample Input 2

byebye

Sample Output 2

-1

If there is no prime number satisfying the condition, output -1.

Sample Input 3

coconut

Sample Output 3

1010237

Problem Statement

A preliminary round of a quiz competition was held. There are N participants, numbered 1 to N, and at most M of them can pass the preliminary round.

The preliminary round consists of K two-choice quiz questions, and the answer to each question is o or x.
Participant i's answer to the j-th question is given as the j-th character of the string S_i.
The correct answer to the j-th question is given as the j-th character of the string T.

The qualifiers are determined by the following procedure.

• Initially, the numbers of qualifiers and non-qualifiers are both 0; all N participants are undetermined.
• For k=1,2,\dots,K in this order, perform the following process.
  • If the number of qualifiers plus the number of undetermined participants who answered the k-th question correctly is at most M, then all undetermined participants who answered the k-th question correctly become qualifiers.
  • Otherwise, all undetermined participants who answered the k-th question incorrectly become non-qualifiers.
• All remaining undetermined participants become non-qualifiers.

You are given Q queries in the following format. Process them in order.

• Integers i and j are given. Change participant i's answer to the j-th question from o to x, or from x to o. Then, determine whether participant i passes the preliminary round.

The change of the answer in each query remains in effect when processing subsequent queries as well.

Constraints

• 1 \leq M \leq N \leq 3\times 10^4
• 1 \leq K \leq 200
• S_i and T are strings of length K consisting of o and x.
• 1 \leq Q \leq 5\times 10^4
• For each query, 1\leq i \leq N and 1 \leq j \leq K.

Sample Input 1

5 3 3
oxo
oxo
oxx
xxo
xox
xoo
3
5 1
1 3
4 1

Sample Output 1

Yes
Yes
No

• Before the first query, participants 1,2 pass on the first question and participant 3 passes on the second question, so the qualifiers are the three participants 1,2,3.
• After the first query, participants 1,2,5 pass on the first question, so the qualifiers are the three participants 1,2,5. Since participant 5 passes the preliminary round, output Yes.
• After the second query, participants 1,2,5 still pass on the first question, so the qualifiers are the three participants 1,2,5. Since participant 1 passes the preliminary round, output Yes.
• After the third query, participant 3 is eliminated on the first question, participants 1,2 pass on the second question, and participant 5 passes on the third question, so the qualifiers remain the three participants 1,2,5. Since participant 4 does not pass the preliminary round, output No.

Sample Input 2

3 1 2
ox
xo
oo
ox
4
3 1
1 1
2 2
1 2

Sample Output 2

No
No
Yes
No

Sample Input 3

1 1 1
o
o
2
1 1
1 1

Sample Output 3

No
Yes

Problem Statement

There is a grid with H rows and W columns. Let the cell at the i-th row from the top and j-th column from the left be denoted as cell (i, j).

Each cell of the grid is painted white or black: cell (i, j) is white if the j-th character of S_i is ., and black if it is #.

You can perform the following operation at most once.

• Choose a rectangular region, and paint all cells within that region black. More formally, choose integers h_1, h_2, w_1, w_2 satisfying 1 \leq h_1 \leq h_2 \leq H and 1 \leq w_1 \leq w_2 \leq W, and paint cell (h, w) black for every pair of integers (h, w) satisfying h_1 \leq h \leq h_2 and w_1 \leq w \leq w_2.

Find the number of possible states of the grid that can be obtained. Here, two states of the grid are considered different if there exists a pair of integers (i, j) satisfying 1 \leq i \leq H and 1 \leq j \leq W such that cell (i, j) is painted white in one state and painted black in the other state.

Constraints

• 1 \leq H, W
• H \times W \leq 2 \times 10^5
• H and W are integers.
• S_i is a string of length W consisting of . and #.

Sample Input 1

2 3
#..
.##

Sample Output 1

7

The possible states of the grid obtainable by performing the operation at most once are the following seven:

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

Sample Input 2

4 1
#
#
#
#

Sample Output 2

1

Sample Input 3

5 5
..##.
..#.#
.##.#
....#
##.##

Sample Output 3

96

Problem Statement

You are given integers N and D, each at least 2.

Among the positive integers at most N that are not multiples of D, find one with the maximum number of positive divisors. If there are multiple such positive integers, output any one of them.

You are given T test cases; solve each of them.

Constraints

• 1 \leq T \leq 10
• 2 \leq D \leq N \leq 10^{18}
• All input values are integers.

Sample Input 1

4
10 2
17 4
2026 919
1000000000000 48

Sample Output 1

9
15
1680
843291048600

The positive integers at most 10 that are not multiples of 2 are the five integers 1, 3, 5, 7, 9, and the numbers of their positive divisors are 1, 2, 2, 2, 3, respectively. Therefore, output 9 for the first test case.

For the second test case, besides 15 in the sample output, outputting any of 6, 10, 14 is also accepted.