Problem Statement

There is a stack of N cards, and the i-th card from the top has an integer A_i written on it.

You take K cards from the bottom of the stack and place them on top of the stack, maintaining their order.

Print the integers written on the cards from top to bottom after the operation.

Constraints

• 1 \leq K < N \leq 100
• 1 \leq A_i \leq 100
• All input values are integers.

Sample Input 1

5 3
1 2 3 4 5

Sample Output 1

3 4 5 1 2

Initially, the integers written on the cards are 1,2,3,4,5 from top to bottom.

After taking three cards from the bottom of the stack and placing them on top, the integers written on the cards become 3,4,5,1,2 from top to bottom.

Sample Input 2

6 2
1 2 1 2 1 2

Sample Output 2

1 2 1 2 1 2

The integers written on the cards are not necessarily distinct.

Problem Statement

Given a length-3 string S consisting of uppercase English letters, print Yes if S equals one of ACE, BDF, CEG, DFA, EGB, FAC, and GBD; print No otherwise.

Constraints

• S is a length-3 string consisting of uppercase English letters.

Sample Input 1

ABC

Sample Output 1

No

When S = ABC, S does not equal any of ACE, BDF, CEG, DFA, EGB, FAC, and GBD, so No should be printed.

Sample Input 2

FAC

Sample Output 2

Yes

Sample Input 3

XYX

Sample Output 3

No

Problem Statement

There is a grid of 64 squares with 8 rows and 8 columns. Let (i,j) denote the square at the i-th row from the top (1\leq i\leq8) and j-th column from the left (1\leq j\leq8).

Each square is either empty or has a piece placed on it. The state of the squares is represented by a sequence (S_1,S_2,S_3,\ldots,S_8) of 8 strings of length 8. Square (i,j) (1\leq i\leq8,1\leq j\leq8) is empty if the j-th character of S_i is ., and has a piece if it is #.

You want to place your piece on an empty square in such a way that it cannot be captured by any of the existing pieces.

A piece placed on square (i,j) can capture pieces that satisfy either of the following conditions:

• Placed on a square in row i
• Placed on a square in column j

For example, a piece placed on square (4,4) can capture pieces placed on the squares shown in blue in the following figure:

How many squares can you place your piece on?

Constraints

• Each S_i is a string of length 8 consisting of . and # (1\leq i\leq 8).

Sample Input 1

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

Sample Output 1

4

The existing pieces can capture pieces placed on the squares shown in blue in the following figure:

Therefore, you can place your piece without it being captured on 4 squares: square (6,6), square (6,7), square (7,6), and square (7,7).

Sample Input 2

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

Sample Output 2

64

There may be no pieces on the grid.

Sample Input 3

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

Sample Output 3

4

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

A repunit is an integer whose digits are all 1 in decimal representation. The repunits in ascending order are 1, 11, 111, \ldots.

Find the N-th smallest integer that can be expressed as the sum of exactly three repunits.

Constraints

• N is an integer between 1 and 333, inclusive.

Sample Input 1

5

Sample Output 1

113

The integers that can be expressed as the sum of exactly three repunits are 3, 13, 23, 33, 113, \ldots in ascending order. For example, 113 can be expressed as 113 = 1 + 1 + 111.

Note that the three repunits do not have to be distinct.

Sample Input 2

19

Sample Output 2

2333

Sample Input 3

333

Sample Output 3

112222222233

Problem Statement

There are N points numbered 1 through N on a two-dimensional plane. Point i (1\le i\le N) has coordinates (X_i,Y_i). Here, it is guaranteed that X and Y are each permutations of (1,2,\ldots,N).

Find the number of values of i such that the interior (not including the boundary) of the rectangle with sides parallel to the x-axis and y-axis, with lower-left vertex (0,0) and upper-right vertex (X_i,Y_i), contains none of the N points numbered 1 through N.

Constraints

• 1\le N\le 3\times 10^5
• 1\le X_i,Y_i\le N
• X and Y are each permutations of (1,2,\ldots,N).
• All input values are integers.

Sample Input 1

3
2 1
1 3
3 2

Sample Output 1

2

The two values i=1,2 satisfy the condition.

For i=3, the interior (not including the boundary) of the rectangle with sides parallel to the x-axis, with lower-left vertex (0,0) and upper-right vertex (3,2), contains point 1.

Sample Input 2

5
1 1
4 2
2 3
5 5
3 4

Sample Output 2

1

Sample Input 3

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

Sample Output 3

2

Problem Statement

N cards, numbered 1 through N, are arranged in a line. For each i\ (1\leq i < N), card i and card (i+1) are adjacent to each other. Card i has A_i written on its front, and B_i written on its back. Initially, all cards are face up.

Consider flipping zero or more cards chosen from the N cards. Among the 2^N ways to choose the cards to flip, find the number, modulo 998244353, of such ways that:

• when the chosen cards are flipped, for every pair of adjacent cards, the integers written on their face-up sides are different.

Constraints

• 1\leq N \leq 2\times 10^5
• 1\leq A_i,B_i \leq 10^9
• All values in the input are integers.

Sample Input 1

3
1 2
4 2
3 4

Sample Output 1

4

Let S be the set of card numbers to flip.

For example, when S=\{2,3\} is chosen, the integers written on their visible sides are 1,2, and 4, from card 1 to card 3, so it satisfies the condition.

On the other hand, when S=\{3\} is chosen, the integers written on their visible sides are 1,4, and 4, from card 1 to card 3, where the integers on card 2 and card 3 are the same, violating the condition.

Four S satisfy the conditions: \{\},\{1\},\{2\}, and \{2,3\}.

Sample Input 2

4
1 5
2 6
3 7
4 8

Sample Output 2

16

Sample Input 3

8
877914575 602436426
861648772 623690081
476190629 262703497
971407775 628894325
822804784 450968417
161735902 822804784
161735902 822804784
822804784 161735902

Sample Output 3

48

Problem Statement

We have a directed graph with N vertices, numbered 1, 2, \ldots, N.

Information about the edges is given by N^2 characters C_{1, 1}, C_{1, 2}, \ldots, C_{1, N}, C_{2, 1}, \ldots, C_{N, N}. Here, each C_{i, j} is either a lowercase English letter or -.

If C_{i, j} is a lowercase English letter, then there is exactly one directed edge from vertex i to vertex j labeled C_{i, j}. If C_{i, j} is -, there is no edge from vertex i to vertex j.

For each integer pair (i, j) with 1 \leq i, j \leq N, answer the following question:

• Among all (not necessarily simple) paths from vertex i to vertex j whose concatenation of labels on the edges forms a palindrome, what is the length of the shortest such path? If there is no such path, the answer is -1.

Constraints

• 1 \leq N \leq 100
• N is an integer.
• Each C_{i, j} is either a lowercase English letter or -.

Sample Input 1

4
ab--
--b-
---a
c---

Sample Output 1

0 1 2 4
-1 0 1 -1
3 -1 0 1
1 -1 -1 0

For example, consider the case (i, j) = (1, 4).
By taking the path 1 \to 1 \to 2 \to 3 \to 4, and concatenating the labels on its edges in order, we get the string abba, which is a palindrome.
There is no path of length at most 3 from vertex 1 to vertex 4 whose concatenation of labels is a palindrome. Thus, the answer for (1, 4) is 4.

Note that the empty string is also a palindrome.

Sample Input 2

5
us---
-st--
--s--
u--s-
---ts

Sample Output 2

0 1 3 -1 -1
-1 0 1 -1 -1
-1 -1 0 -1 -1
1 3 -1 0 -1
-1 -1 5 1 0

Problem Statement

The Kingdom of AtCoder is composed of N towns and N-1 roads.
The towns are labeled as Town 1, Town 2, \dots, Town N. Similarly, the roads are labeled as Road 1, Road 2, \dots, Road N-1. Road i connects Towns A_i and B_i bidirectionally, and you have to pay the toll of C_i to go through it. For every pair of different towns (i, j), it is possible to go from Town A_i to Town B_j via the roads.

You are given a sequence D = (D_1, D_2, \dots, D_N), where D_i is the cost to do sightseeing in Town i. Let us define the travel cost E_{i,j} from Town i to Town j as the total toll incurred when going from Town i to Town j, plus D_{j}.

• More formally, E_{i,j} is defined as D_j + \displaystyle\sum_{l=0}^{k-1} c_l, where the shortest path between i and j is i = p_0, p_1, \dots, p_{k-1}, p_k = j and the toll for the road connecting Towns p_{l} and p_{l+1} is c_l.

For every i, find the maximum possible travel cost when traveling from Town i to another town.

• More formally, for every i, find \max_{1 \leq j \leq N, j \neq i} E_{i,j}.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq N (1 \leq i \leq N-1)
• 1 \leq B_i \leq N (1 \leq i \leq N-1)
• 1 \leq C_i \leq 10^9 (1 \leq i \leq N-1)
• 1 \leq D_i \leq 10^9 (1 \leq i \leq N)
• It is possible to travel from Town i to Town j via some number of roads, for a pair of integers (i,j) such that 1 \leq i \lt j \leq N.
• All values in input are integers.

Sample Input 1

3
1 2 2
2 3 3
1 2 3

Sample Output 1

8
6
6

The value of E_{i,j} for every ordered pair of towns (i,j) is as follows.

• E_{1,2} = 2 + 2 = 4
• E_{1,3} = 5 + 3 = 8
• E_{2,1} = 2 + 1 = 3
• E_{2,3} = 3 + 3 = 6
• E_{3,1} = 5 + 1 = 6
• E_{3,2} = 3 + 2 = 5

Sample Input 2

6
1 2 3
1 3 1
1 4 4
1 5 1
1 6 5
9 2 6 5 3 100

Sample Output 2

105
108
106
109
106
14

Sample Input 3

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

Sample Output 3

5000000006
4000000006
3000000006
3000000001
4000000001
5000000001