Problem Statement

The number pi to the 100-th decimal place is

3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679.

You are given an integer N between 1 and 100, inclusive.

Print the value of pi to the N-th decimal place.

More precisely, truncate the value of pi to N decimal places and print the result without removing the trailing 0s.

Constraints

• 1\leq N\leq 100
• N is an integer.

Sample Input 1

2

Sample Output 1

3.14

Truncating the value of pi to 2 decimal places results in 3.14. Thus, you should print 3.14.

Sample Input 2

32

Sample Output 2

3.14159265358979323846264338327950

Do not remove the trailing 0s.

Sample Input 3

100

Sample Output 3

3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679

Problem Statement

You are given a string S consisting of lowercase English letters and the character ..
Print the last substring when S is split by .s.
In other words, print the longest suffix of S that does not contain ..

Constraints

• S is a string of length between 2 and 100, inclusive, consisting of lowercase English letters and ..
• S contains at least one ..
• S does not end with ..

Sample Input 1

atcoder.jp

Sample Output 1

jp

The longest suffix of atcoder.jp that does not contain . is jp.

Sample Input 2

translate.google.com

Sample Output 2

com

S may contain multiple .s.

Sample Input 3

.z

Sample Output 3

z

S may start with ..

Sample Input 4

..........txt

Sample Output 4

txt

S may contain consecutive .s.

Problem Statement

You are given two strings S and T consisting of lowercase English letters.

Determine if there exists a pair of integers c and w such that 1 \leq c \leq w < |S| and the following condition is satisfied. Here, |S| denotes the length of the string S. Note that w must be less than |S|.

• If S is split at every w characters from the beginning, the concatenation of the c-th characters of the substrings of length at least c in order equals T.

Constraints

• S and T are strings consisting of lowercase English letters.
• 1 \leq |T| \leq |S| \leq 100

Sample Input 1

atcoder toe

Sample Output 1

Yes

If S is split at every two characters, it looks like this:

at
co
de
r

Then, the concatenation of the 2nd characters of the substrings of length at least 2 is toe, which equals T. Thus, print Yes.

Sample Input 2

beginner r

Sample Output 2

No

w=|S| is not allowed, and no pair of integers 1 \leq c \leq w < |S| satisfies the condition. Thus, print No.

Sample Input 3

verticalreading agh

Sample Output 3

No

Problem Statement

There is a grid with H horizontal rows and W vertical columns. Each cell has a lowercase English letter written on it. We denote by (i, j) the cell at the i-th row from the top and j-th column from the left.

The letters written on the grid are represented by H strings S_1,S_2,\ldots, S_H, each of length W. The j-th letter of S_i represents the letter written on (i, j).

There is a unique set of contiguous cells (going vertically, horizontally, or diagonally) in the grid with s, n, u, k, and e written on them in this order.
Find the positions of such cells and print them in the format specified in the Output section.

A tuple of five cells (A_1,A_2,A_3,A_4,A_5) is said to form a set of contiguous cells (going vertically, horizontally, or diagonally) with s, n, u, k, and e written on them in this order if and only if all of the following conditions are satisfied.

• A_1,A_2,A_3,A_4 and A_5 have letters s, n, u, k, and e written on them, respectively.
• For all 1\leq i\leq 4, cells A_i and A_{i+1} share a corner or a side.
• The centers of A_1,A_2,A_3,A_4, and A_5 are on a common line at regular intervals.

Constraints

• 5\leq H\leq 100
• 5\leq W\leq 100
• H and W are integers.
• S_i is a string of length W consisting of lowercase English letters.
• The given grid has a unique conforming set of cells.

Sample Input 1

6 6
vgxgpu
amkxks
zhkbpp
hykink
esnuke
zplvfj

Sample Output 1

5 2
5 3
5 4
5 5
5 6

Tuple (A_1,A_2,A_3,A_4,A_5)=((5,2),(5,3),(5,4),(5,5),(5,6)) satisfies the conditions.
Indeed, the letters written on them are s, n, u, k, and e;
for all 1\leq i\leq 4, cells A_i and A_{i+1} share a side;
and the centers of the cells are on a common line.

Sample Input 2

5 5
ezzzz
zkzzz
ezuzs
zzznz
zzzzs

Sample Output 2

5 5
4 4
3 3
2 2
1 1

Tuple (A_1,A_2,A_3,A_4,A_5)=((5,5),(4,4),(3,3),(2,2),(1,1)) satisfies the conditions.
However, for example, (A_1,A_2,A_3,A_4,A_5)=((3,5),(4,4),(3,3),(2,2),(3,1)) violates the third condition because the centers of the cells are not on a common line, although it satisfies the first and second conditions.

Sample Input 3

10 10
kseeusenuk
usesenesnn
kskekeeses
nesnusnkkn
snenuuenke
kukknkeuss
neunnennue
sknuessuku
nksneekknk
neeeuknenk

Sample Output 3

9 3
8 3
7 3
6 3
5 3

Problem Statement

Takahashi is standing at the coordinate 0 on a number line.

He will now perform N jumps. In the i-th jump (1 \leq i \leq N), he moves a_i or b_i in the positive direction.

Is it possible for him to be at the coordinate X after N jumps?

Constraints

• 1 \leq N \leq 100
• 1 \leq a_i \lt b_i \leq 100 \, (1 \leq i \leq N)
• 1 \leq X \leq 10000
• All values in input are integers.

Sample Input 1

2 10
3 6
4 5

Sample Output 1

Yes

By moving b_1 (= 6) in the first jump and a_2 (= 4) in the second jump, he can be at the coordinate X (= 10).

Sample Input 2

2 10
10 100
10 100

Sample Output 2

No

He can be at the coordinate X (= 10) after the first jump, but not after all jumps.

Sample Input 3

4 12
1 8
5 7
3 4
2 6

Sample Output 3

Yes

Problem Statement

Snuke the doctor prescribed N kinds of medicine for Takahashi. For the next a_i days (including the day of the prescription), he has to take b_i pills of the i-th medicine. He does not have to take any other medicine.

Let the day of the prescription be day 1. On or after day 1, when is the first day on which he has to take K pills or less?

Constraints

• 1 \leq N \leq 3 \times 10^5
• 0 \leq K \leq 10^9
• 1 \leq a_i,b_i \leq 10^9
• All input values are integers.

Sample Input 1

4 8
6 3
2 5
1 9
4 2

Sample Output 1

3

On day 1, he has to take 3,5,9, and 2 pills of the 1-st, 2-nd, 3-rd, and 4-th medicine, respectively. In total, he has to take 19 pills on this day, which is not K(=8) pills or less.
On day 2, he has to take 3,5, and 2 pills of the 1-st, 2-nd, and 4-th medicine, respectively. In total, he has to take 10 pills on this day, which is not K(=8) pills or less.
On day 3, he has to take 3 and 2 pills of the 1-st and 4-th medicine, respectively. In total, he has to take 5 pills on this day, which is K(=8) pills or less for the first time.

Thus, the answer is 3.

Sample Input 2

4 100
6 3
2 5
1 9
4 2

Sample Output 2

1

Sample Input 3

15 158260522
877914575 2436426
24979445 61648772
623690081 33933447
476190629 62703497
211047202 71407775
628894325 31963982
822804784 50968417
430302156 82631932
161735902 80895728
923078537 7723857
189330739 10286918
802329211 4539679
303238506 17063340
492686568 73361868
125660016 50287940

Sample Output 3

492686569

Problem Statement

There is a grid with H horizontal rows and W vertical columns. (i, j) denotes the square at the i-th row from the top and j-th column from the left.
N squares, (r_1, c_1), (r_2, c_2), \ldots, (r_N, c_N), have walls.

Takahashi is initially at square (r_\mathrm{s}, c_\mathrm{s}).

Q instructions are given to Takahashi. For i = 1, 2, \ldots, Q, the i-th instruction is represented by a pair of a character d_i and a positive integer l_i. d_i is one of L, R, U, and D, representing the directions of left, right, up, and down, respectively.

Given the i-th direction, Takahashi repeats the following action l_i times:

If a square without a wall is adjacent to the current square in the direction represented by d_i, move to that square; otherwise, do nothing.

For i = 1, 2, \ldots, Q, print the square where Takahashi will be after he follows the first i instructions.

Constraints

• 2 \leq H, W \leq 10^9
• 1 \leq r_\mathrm{s} \leq H
• 1 \leq c_\mathrm{s} \leq W
• 0 \leq N \leq 2 \times 10^5
• 1 \leq r_i \leq H
• 1 \leq c_i \leq W
• i \neq j \Rightarrow (r_i, c_i) \neq (r_j, c_j)
• (r_\mathrm{s}, c_\mathrm{s}) \neq (r_i, c_i) for all i = 1, 2, \ldots, N.
• 1 \leq Q \leq 2 \times 10^5
• d_i is one of the characters L, R, U, and D.
• 1 \leq l_i \leq 10^9
• All values in the input other than d_i are integers.

Sample Input 1

5 5 4 4
3
5 3
2 2
1 4
4
L 2
U 3
L 2
R 4

Sample Output 1

4 2
3 2
3 1
3 5

The given grid and the initial position of Takahashi are as follows, where # denotes a square with a wall, T a square where Takahashi is, and . the other squares:

...#.
.#...
.....
...T.
..#..

Given the 1-st instruction, Takahashi moves 2 squares to the left, ending up in square (4, 2) as follows:

...#.
.#...
.....
.T...
..#..

Given the 2-nd instruction, Takahashi first moves 1 square upward, then he "does nothing" twice because the adjacent square in his direction has a wall. As a result, he ends up in square (3, 2) as follows:

...#.
.#...
.T...
.....
..#..

Given the 3-rd instruction, Takahashi first moves 1 square to the left, then he "does nothing" once because there is no square in his direction. As a result, he ends up in square (3, 1) as follows:

...#.
.#...
T....
.....
..#..

Given the 4-th instruction, Takahashi moves 4 squares to the right, ending up in square (3, 5) as follows:

...#.
.#...
....T
.....
..#..

Sample Input 2

6 6 6 3
7
3 1
4 3
2 6
3 4
5 5
1 1
3 2
10
D 3
U 3
L 2
D 2
U 3
D 3
U 3
R 3
L 3
D 1

Sample Output 2

6 3
5 3
5 1
6 1
4 1
6 1
4 1
4 2
4 1
5 1

Problem Statement

Find the number, modulo 998244353, of integer tuples (a, b, c) that satisfy the following conditions.

• 1 \leq a,b,c \leq N
• a,b,c are pairwise distinct.
• The remainder when a is divided by b is equal to c.

Constraints

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

Sample Input 1

7

Sample Output 1

12

There are 12 integer tuples (a,b,c) that satisfy the conditions:

• (3,2,1)
• (4,3,1)
• (5,2,1)
• (5,3,2)
• (5,4,1)
• (6,4,2)
• (6,5,1)
• (7,2,1)
• (7,3,1)
• (7,4,3)
• (7,5,2)
• (7,6,1)

Sample Input 2

441

Sample Output 2

94700

Sample Input 3

411111111114

Sample Output 3

462474062

Problem Statement

There are N scaffolds numbered from 1 to N arranged in a line. The height of scaffold i(1 \leq i \leq N) is H_i.

Takahashi decides to play a game of moving on the scaffolds. Initially, he freely chooses an integer i(1 \leq i \leq N) and gets on scaffold i.

When he is on scaffold i at some point, he can choose an integer j(1 \leq j \leq N) satisfying the following condition and move to scaffold j:

• H_j \leq H_i - D and 1 \leq |i-j| \leq R.

Find the maximum number of moves he can make when he repeats moving until he can no longer move.

Constraints

• 1 \leq N \leq 5 \times 10^5
• 1 \leq D,R \leq N
• H is a permutation of (1,2,\ldots,N).
• All input values are integers.

Sample Input 1

5 2 1
5 3 1 4 2

Sample Output 1

2

Takahashi initially gets on scaffold 1 and can move between the scaffolds as follows:

• First move: Since H_2 \leq H_1 -D and |2-1| \leq R, he can move to scaffold 2. Move from scaffold 1 to scaffold 2.
• Second move: Since H_3 \leq H_2 -D and |3-2| \leq R, he can move to scaffold 3. Move from scaffold 2 to scaffold 3.
• Since the height of scaffold 3 is 1, he can no longer move.

As shown above, he can move 2 times. Also, no matter how he chooses the scaffolds to move to, he cannot move 3 or more times. Therefore, output 2.

Sample Input 2

13 3 2
13 7 10 1 9 5 4 11 12 2 8 6 3

Sample Output 2

3