Problem Statement

You are given a string S, which represents a weather forecast for the seven days starting tomorrow.
The i-th of those seven days is forecast to be sunny if the i-th character of S is o, and rainy if that character is x.

Tell us whether the N-th day is forecast to be sunny.

Constraints

• N is an integer between 1 and 7 (inclusive).
• S is a string of length 7 consisting of o and x.

Sample Input 1

4
oooxoox

Sample Output 1

No

The forecast for each of the seven days starting tomorrow is as follows: sunny, sunny, sunny, rainy, sunny, sunny, rainy.
In particular, the fourth day is forecast to be rainy.

Sample Input 2

7
ooooooo

Sample Output 2

Yes

Problem Statement

There are N people numbered 1, 2, \ldots, N, sitting in this clockwise order around a round table. In particular, person 1 is sitting next to person N in the clockwise direction.

For each i = 1, 2, \ldots, N, person i has a name S_i and an age A_i. Here, no two people have the same name or the same age.

Starting from the youngest person, print the names of all N people in the order of their seating positions in clockwise order.

Constraints

• 2 \leq N \leq 100
• N is an integer.
• S_i is a string of length between 1 and 10, consisting of lowercase English letters.
• i \neq j \implies S_i \neq S_j
• 0 \leq A_i \leq 10^9
• A_i is an integer.
• i \neq j \implies A_i \neq A_j

Sample Input 1

5
alice 31
bob 41
carol 5
dave 92
ellen 65

Sample Output 1

carol
dave
ellen
alice
bob

The youngest person is person 3. Therefore, starting from person 3, print the names in the clockwise order of their seating positions: person 3, person 4, person 5, person 1, and person 2.

Sample Input 2

2
takahashi 1000000000
aoki 999999999

Sample Output 2

aoki
takahashi

Problem Statement

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

Determine whether the string S satisfies the following condition:

• Every uppercase letter in S that is not at the beginning is immediately preceded by a character contained in T. More formally, for all integers i such that 2 \leq i \leq |S|, if the i-th character of S is uppercase, then the (i-1)-th character of S is contained in T.

Constraints

• Each of S and T is a string consisting of lowercase and uppercase English letters with length between 1 and 100, inclusive.

Sample Input 1

AtCoder
Total

Sample Output 1

Yes

The only uppercase letter in S that is not at the beginning is the 3rd character C. The immediately preceding character t is contained in T, so output Yes.

Sample Input 2

aBCdE
abcdcba

Sample Output 2

No

The 3rd character of S is the uppercase letter C, and its immediately preceding character is B, but B is not contained in T.

Sample Input 3

abcde
XYZ

Sample Output 3

Yes

Problem Statement

We have 4 cards with an integer 1 written on it, 4 cards with 2, \ldots, 4 cards with N, for a total of 4N cards.

Takahashi shuffled these cards, removed one of them, and gave you a pile of the remaining 4N-1 cards. The i-th card (1 \leq i \leq 4N - 1) of the pile has an integer A_i written on it.

Find the integer written on the card removed by Takahashi.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq A_i \leq N \, (1 \leq i \leq 4N - 1)
• For each k \, (1 \leq k \leq N), there are at most 4 indices i such that A_i = k.
• All values in input are integers.

Sample Input 1

3
1 3 2 3 3 2 2 1 1 1 2

Sample Output 1

3

Takahashi removed a card with 3 written on it.

Sample Input 2

1
1 1 1

Sample Output 2

1

Sample Input 3

4
3 2 1 1 2 4 4 4 4 3 1 3 2 1 3

Sample Output 3

2

Problem Statement

There is a 9\times 9 grid A, where each cell contains an integer between 1 and 9, inclusive.
Specifically, the cell at the i-th row from the top and j-th column from the left contains A_{i,j}.

If A satisfies all of the following conditions, print Yes. Otherwise, print No.

• For each row of A, the nine cells in that row contain each integer from 1 to 9 exactly once.
• For each column of A, the nine cells in that column contain each integer from 1 to 9 exactly once.
• Divide the rows of A into three groups, each of three rows, from top to bottom, and similarly divide the columns into three groups, each of three columns, from left to right. Each 3\times 3 grid obtained from A in this way contains each integer from 1 to 9 exactly once.

Constraints

• 1\leq A_{i,j}\leq 9
• All input values are integers.

Sample Input 1

1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 3 4 5 6 7 8 9 1
5 6 7 8 9 1 2 3 4
8 9 1 2 3 4 5 6 7
3 4 5 6 7 8 9 1 2
6 7 8 9 1 2 3 4 5
9 1 2 3 4 5 6 7 8

Sample Output 1

Yes

The grid A is shown below.

The grid A satisfies all three conditions, so print Yes.

Sample Input 2

1 2 3 4 5 6 7 8 9
2 3 4 5 6 7 8 9 1
3 4 5 6 7 8 9 1 2
4 5 6 7 8 9 1 2 3
5 6 7 8 9 1 2 3 4
6 7 8 9 1 2 3 4 5
7 8 9 1 2 3 4 5 6
8 9 1 2 3 4 5 6 7
9 1 2 3 4 5 6 7 8

Sample Output 2

No

The grid A is shown below.

For example, if you look at the top left 3\times 3 grid, you can see that the third condition is unsatisfied, so print No.

Sample Input 3

1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6

Sample Output 3

No

The grid A is shown below.

For example, if you look at the leftmost column, you can see that the second condition is unsatisfied, so print No.

Problem Statement

The decimal representation of 414 is 414, which is a palindrome. Also, the octal representation of 414 is 636, which is also a palindrome. Based on this, solve the following problem.

You are given positive integers A and N. Find the sum of all integers between 1 and N, inclusive, whose decimal representation and base-A representation are both palindromes.

Under the constraints of this problem, it can be proved that the answer is less than 2^{63}.

Constraints

• 2 \leq A \leq 9
• 1 \leq N \le 10^{12}
• All input values are integers.

Sample Input 1

8
1000

Sample Output 1

2155

The integers satisfying the condition are 1,2,3,4,5,6,7,9,121,292,333,373,414,585 (14 integers), and their sum is 2155.

Sample Input 2

8
999999999999

Sample Output 2

914703021014

Sample Input 3

6
999999999999

Sample Output 3

283958331810

Problem Statement

You are given an integer sequence A=(A_1,A_2,\dots,A_N) of length N.

Find the maximum value of \displaystyle \sum_{i=1}^{M} i \times B_i for a (not necessarily contiguous) subsequence B=(B_1,B_2,\dots,B_M) of length M of A.

Notes

A subsequence of a number sequence is a sequence that is obtained by removing 0 or more elements from the original number sequence and concatenating the remaining elements without changing the order.

For example, (10,30) is a subsequence of (10,20,30), but (20,10) is not a subsequence of (10,20,30).

Constraints

• 1 \le M \le N \le 2000
• - 2 \times 10^5 \le A_i \le 2 \times 10^5
• All values in input are integers.

Sample Input 1

4 2
5 4 -1 8

Sample Output 1

21

When B=(A_1,A_4), we have \displaystyle \sum_{i=1}^{M} i \times B_i = 1 \times 5 + 2 \times 8 = 21. Since it is impossible to achieve 22 or a larger value, the solution is 21.

Sample Input 2

10 4
-3 1 -4 1 -5 9 -2 6 -5 3

Sample Output 2

54

Problem Statement

The manufacturing of a certain product requires N processes numbered 1,2,\dots,N.

For each process i, there are two types of machines S_i and T_i available for purchase to handle it.

• Machine S_i: Can process A_i products per day per unit, and costs P_i yen per unit.
• Machine T_i: Can process B_i products per day per unit, and costs Q_i yen per unit.

You can purchase any number of each machine, possibly zero.

Suppose that process i can handle W_i products per day as a result of introducing machines.
Here, we define the production capacity as the minimum of W, that is, \displaystyle \min^{N}_{i=1} W_i.

Given a total budget of X yen, find the maximum achievable production capacity.

Constraints

• All input values are integers.
• 1 \le N \le 100
• 1 \le A_i,B_i \le 100
• 1 \le P_i,Q_i,X \le 10^7

Sample Input 1

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

Sample Output 1

4

For example, by introducing machines as follows, we can achieve a production capacity of 4, which is the maximum possible.

• For process 1, introduce 2 units of machine S_1.
  • This allows processing 4 products per day and costs a total of 10 yen.
• For process 2, introduce 1 unit of machine S_2.
  • This allows processing 1 product per day and costs a total of 1 yen.
• For process 2, introduce 1 unit of machine T_2.
  • This allows processing 3 products per day and costs a total of 3 yen.
• For process 3, introduce 2 units of machine T_3.
  • This allows processing 4 products per day and costs a total of 8 yen.

Sample Input 2

1 10000000
100 1 100 1

Sample Output 2

1000000000

Sample Input 3

1 1
1 10000000 1 10000000

Sample Output 3

0

There may be cases where a positive production capacity cannot be achieved.

Sample Input 4

10 7654321
8 6 9 1
5 6 4 3
2 4 7 9
7 8 9 1
7 9 1 6
4 8 9 1
2 2 8 9
1 6 2 6
4 2 3 4
6 6 5 2

Sample Output 4

894742

Problem Statement

You are given a directed graph G with N vertices and M edges.
The vertices of G are numbered as vertex 1, vertex 2, \ldots, vertex N, and the i-th edge (1\leq i\leq M) goes from vertex U_i to vertex V_i.

Solve the following problem for k=1,2,\ldots,N.

Takahashi's goal is to delete some (possibly zero) vertices from G, along with all edges having those vertices as an endpoint, so that the following condition is satisfied.

• The only vertices reachable from vertex 1 by traversing zero or more edges are vertices 1,2,\ldots,k.

Determine whether he can achieve his goal, and if so, find the minimum number of vertices he needs to delete to achieve it.

Constraints

• 2\leq N\leq 3\times 10^5
• 1\leq M\leq 3\times 10^5
• 1\leq U_i,V_i\leq N
• All input values are integers.

Sample Input 1

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

Sample Output 1

1
2
-1
1
0

• For k=1, the goal can be achieved by deleting vertex 2. Note that vertices 3,4,5 are already unreachable from vertex 1 without deleting them. The goal cannot be achieved without deleting at least one vertex, so output 1 on the first line.
• For k=2, the goal can be achieved by deleting vertices 4 and 5. It is impossible to achieve the goal by deleting one or fewer vertices, so output 2 on the second line.
• For k=3, Takahashi cannot achieve the goal no matter how he deletes vertices. Thus, output -1 on the third line.
• For k=4, the goal can be achieved by deleting vertex 5. The goal cannot be achieved without deleting at least one vertex, so output 1 on the fourth line.
• For k=5, the goal can be achieved without deleting any vertices. Thus, output 0 on the fifth line.

Sample Input 2

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

Sample Output 2

1
0
-1
-1
-1

G is not necessarily connected. Also, G may have multi-edges or self-loops.