Problem Statement

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

Output the string obtained by appending s to the end of the string S.

Constraints

• S is a string of length between 1 and 10, inclusive, consisting of lowercase English letters.

Sample Input 1

http

Sample Output 1

https

Appending s to the end of http results in https, so print https.

Sample Input 2

append

Sample Output 2

appends

Sample Input 3

beginner

Sample Output 3

beginners

Problem Statement

At the annual Setsubun festival, one eats the same number of beans as their age. Takahashi-kun does not eat beans at any other time.
He is N years old at this year's Setsubun (0 years later).

At the earliest, how many years later will he have eaten a total of K or more beans from this year onward (including this year)?
He is immortal, so he will eventually have eaten a total of K or more beans from this year onward.

Constraints

• All input values are integers.
• 1 \le N,K \le 10^8

Sample Input 1

4 43

Sample Output 1

6

• At Setsubun 0 years later, Takahashi-kun eats 4 beans, totaling 4 beans from this year onward.
• At Setsubun 1 year later, he eats 5 beans, totaling 9 beans from this year onward.
• At Setsubun 2 years later, he eats 6 beans, totaling 15 beans from this year onward.
• At Setsubun 3 years later, he eats 7 beans, totaling 22 beans from this year onward.
• At Setsubun 4 years later, he eats 8 beans, totaling 30 beans from this year onward.
• At Setsubun 5 years later, he eats 9 beans, totaling 39 beans from this year onward.
• At Setsubun 6 years later, he eats 10 beans, totaling 49 beans from this year onward.

At Setsubun 6 years later, he will have eaten a total of 43 or more beans, so output 6.

Sample Input 2

100000000 100000000

Sample Output 2

0

The number of beans eaten this year alone may reach K or more.

Sample Input 3

1234 12345678

Sample Output 3

3886

Problem Statement

AtCoder Inc. starts work at time 0 and ends work at time T. The interval between time t and time t+1 is 1 second.
Takahashi-kun views the SNS chokutter during AtCoder Inc.'s business hours according to the following rules:

• He opens chokutter at the same time as work starts.
• If chokutter is open at the moment Aoki-kun passes behind Takahashi-kun's desk, he immediately closes it.
• If Takahashi-kun closes chokutter at time t, he always opens it at time t+100.

From the start to the end of work, Aoki-kun passed behind Takahashi-kun's desk N times, with the i-th time being at time A_i.
From the start to the end of work, for how many seconds in total was Takahashi-kun viewing chokutter?
Aoki-kun never passed behind the desk at the moment when Takahashi-kun opened chokutter.

Constraints

• All input values are integers.
• 0 \le N \le 3 \times 10^5
• 1 \le A_1 < A_2 < \dots < A_N \le T \le 10^9
• Aoki-kun never passes behind the desk at the moment when Takahashi-kun opens chokutter.

Sample Input 1

5 700
100 150 300 350 700

Sample Output 1

500

• At time 0, Takahashi-kun opens chokutter.
• At time 100, Aoki-kun passes behind Takahashi-kun's desk, and Takahashi-kun immediately closes chokutter.
• At time 150, Aoki-kun passes behind Takahashi-kun's desk, but Takahashi-kun does not have chokutter open at this time.
• At time 200, Takahashi-kun opens chokutter again.
• At time 300, Aoki-kun passes behind Takahashi-kun's desk, and Takahashi-kun immediately closes chokutter.
• At time 350, Aoki-kun passes behind Takahashi-kun's desk, but Takahashi-kun does not have chokutter open at this time.
• At time 400, Takahashi-kun opens chokutter again.
• At time 700, Aoki-kun passes behind Takahashi-kun's desk, and Takahashi-kun immediately closes chokutter.

Takahashi-kun was viewing chokutter for a total of 500 seconds.

Sample Input 2

0 1000000000

Sample Output 2

1000000000

There may be cases where Aoki-kun never passes behind Takahashi-kun's desk.

Sample Input 3

10 1234
395 424 588 745 773 863 910 958 1102 1195

Sample Output 3

734

Problem Statement

There is an N \times N grid, and there is one piece placed in each column.
The piece in column i is placed in row R_i from the top.

You can perform the following operation zero or more times:

• Choose a piece that is not in the topmost row and move that piece to the cell directly above it.

Find the minimum number of operations needed to satisfy the following condition for all integers i satisfying 1 \le i \le N-1:

• Let the piece in column i be in row x from the top and the piece in column i+1 be in row y from the top. Then, |x-y| \le 1.

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

Constraints

• All input values are integers.
• 1 \le T \le 50000
• 2 \le N \le 3 \times 10^5
• 1 \le R_i \le N
• For a single input, the sum of N does not exceed 3 \times 10^5.

Sample Input 1

5
5
5 2 1 3 4
2
1 1
3
1 3 1
9
9 9 8 2 4 4 3 5 3
20
7 4 6 2 15 5 17 15 1 8 18 1 5 1 12 11 2 7 8 14

Sample Output 1

4
0
1
16
105

This input contains five test cases.

For the first test case, by performing operations as follows, you can satisfy the condition in the problem statement with four operations, which is the minimum.

• Move the piece in the 5-th column from the left to the cell directly above it. The pieces are in rows 5,2,1,3,3 from left to right.
• Move the piece in the 1-st column from the left to the cell directly above it. The pieces are in rows 4,2,1,3,3 from left to right.
• Move the piece in the 1-st column from the left to the cell directly above it. The pieces are in rows 3,2,1,3,3 from left to right.
• Move the piece in the 4-th column from the left to the cell directly above it. The pieces are in rows 3,2,1,2,3 from left to right.

For the second test case, the condition is satisfied without performing any operations.

Problem Statement

There is an N \times N grid. The cell at the i-th row from the top and j-th column from the left is called (i,j).
The grid is described by N strings S_1,S_2,\dots,S_N. If the j-th character of S_i is ., (i,j) is an empty cell; if it is #, (i,j) is a wall cell.

Initially, Takahashi-kun is at empty cell (N,C), and repeats the following movement N-1 times:

• If he is currently at (r,c), he specifies one of (r-1,c-1),(r-1,c),(r-1,c+1) as the destination. Here, he cannot specify a cell that does not exist in the grid as the destination.
• If the destination (a,b) is a wall cell, the following occurs:
  • If (i,b) is currently an empty cell for all integers satisfying a < i \le N, he destroys the wall at (a,b) and moves there. That is, (a,b) becomes an empty cell and he moves to (a,b).
  • Otherwise, he fails to move. In this case, he immediately ends the repetition of movements, even if he has not made N-1 movements.
• If the destination (a,b) is an empty cell, he moves to (a,b).

Output a string R of length N satisfying the following conditions:

• If he can reach (1,i) without failing during the movements, the i-th character of R is 1.
• Otherwise, the i-th character of R is 0.

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

Constraints

• T,N,C are integers.
• 1 \le T \le 50000
• 2 \le N \le 3000
• 1 \le C \le N
• S_i is a string of length N consisting of . and #.
• The C-th character of S_N is ..
• For each input, the sum of N^2 does not exceed 9 \times 10^6.

Sample Input 1

5
5 3
.###.
..#..
#.#.#
#...#
##..#
2 2
##
..
4 1
####
####
####
.###
3 3
...
...
...
10 3
##.##.##.#
.####..#..
...#.#..#.
.#.#.#.#..
...####...
#.#.##....
.##...#...
#.##.....#
#....###.#
.#..#.#...

Sample Output 1

10111
11
1000
111
0011010010

This input contains five test cases.

For the first test case, for example, he can reach (1,3) without failing during the movements as follows:

• Initially, he is at (5,3).
• He moves to empty cell (4,2).
• (3,3) is a wall cell, but since (4,3),(5,3) are currently both empty cells, he destroys the wall at (3,3) and moves to (3,3).
• (2,3) is a wall cell, but since (3,3),(4,3),(5,3) are currently all empty cells, he destroys the wall at (2,3) and moves to (2,3).
• (1,3) is a wall cell, but since (2,3),(3,3),(4,3),(5,3) are currently all empty cells, he destroys the wall at (1,3) and moves to (1,3).

He can reach (1,1),(1,3),(1,4),(1,5) without failing during the movements, so print 10111.

Problem Statement

A positive integer X is called a good integer if and only if it satisfies the following condition:

• When X is written in decimal notation, the ones digit, tens digit, \ldots form a non-increasing sequence.
  • More formally, the unique non-negative integer sequence (d_0,d_1,\ldots) satisfying \displaystyle X=\sum_{i=0}^{\infty} d_i10^i (0\le d_i < 10) forms a non-increasing sequence.

For example, 112389, 1, and 777 are good integers, but 443 and 404 are not good integers.

You are given a positive integer N.

Determine whether there exists a good integer that is a multiple of N, and if it exists, find its minimum value.

Constraints

• 1\le N\le 3\times 10^6
• All input values are integers.

Sample Input 1

21

Sample Output 1

126

126 is a multiple of 21, and we have 6 \geq 2 \geq 1 \geq 0 \geq \ldots, so it is a good integer. There does not exist a good integer less than 126 that is a multiple of 21, so output 126.

Sample Input 2

10

Sample Output 2

-1

Sample Input 3

3

Sample Output 3

3

Sample Input 4

1089

Sample Output 4

9999999999999999999999

The answer may be 2^{64} or greater.

Problem Statement

You are given integers N,M,A,B.

Define an integer sequence X=(X_0,X_1,\ldots,X_{N-1}) as \displaystyle X_k = (Ak+B) \bmod M.

Find the number of integers k satisfying 0 \le k < N and X_k > k.

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

Constraints

• 1\le T\le 3\times 10^5
• 1\le N \le M\le 10^9
• 0\le A,B < M
• All input values are integers.

Sample Input 1

4
4 6 4 3
7 7 3 1
10 46 0 12
443 2026 131 210

Sample Output 1

2
3
10
395

Consider the first test case.

• When k=0: X_0=(4\times 0+3)\bmod 6=3, so X_k>k holds.
• When k=1: X_1=(4\times 1+3)\bmod 6=1, so X_k>k does not hold.
• When k=2: X_2=(4\times 2+3)\bmod 6=5, so X_k>k holds.
• When k=3: X_3=(4\times 3+3)\bmod 6=3, so X_k>k does not hold.

From the above, the integers k satisfying 0 \le k < 4 and X_k>k are k=0,2, which is two integers. Thus, output 2 on the first line.