Problem Statement

You are given a string S consisting of uppercase and lowercase English letters.
Here, exactly one character of S is uppercase, and the others are all lowercase.
Find the integer x such that the x-th character of S is uppercase.
Here, the initial character of S is considered the 1-st one.

Constraints

• S is a string of length between 2 and 100, inclusive, consisting of uppercase and lowercase English letters.
• S has exactly one uppercase letter.

Sample Input 1

aBc

Sample Output 1

2

The 1-st character of aBc is a, the 2-nd is B, and the 3-rd is c; the 2-nd character is uppercase.
Thus, 2 should be printed.

Sample Input 2

xxxxxxXxxx

Sample Output 2

7

An uppercase letter X occurs as the 7-th character of S=xxxxxxXxxx, so 7 should be printed.

Sample Input 3

Zz

Sample Output 3

1

Problem Statement

Takahashi is participating in a gymnastic competition.
In the competition, each of 5N judges grades Takahashi's performance, and his score is determined as follows:

• Invalidate the grades given by the N judges who gave the highest grades.
• Invalidate the grades given by the N judges who gave the lowest grades.
• Takahashi's score is defined as the average of the remaining 3N judges' grades.

More formally, Takahashi's score is obtained by performing the following procedure on the multiset of the judges' grades S (|S|=5N):

• Repeat the following operation N times: choose the maximum element (if there are multiple such elements, choose one of them) and remove it from S.
• Repeat the following operation N times: choose the minimum element (if there are multiple such elements, choose one of them) and remove it from S.
• Takahashi's score is defined as the average of the 3N elements remaining in S.

The i-th (1\leq i\leq 5N) judge's grade for Takahashi's performance was X_i points. Find Takahashi's score.

Constraints

• 1\leq N\leq 100
• 0\leq X_i\leq 100
• All values in the input are integers.

Sample Input 1

1
10 100 20 50 30

Sample Output 1

33.333333333333336

Since N=1, the grade given by one judge who gave the highest grade, and one with the lowest, are invalidated.
The 2-nd judge gave the highest grade (100 points), which is invalidated.
Additionally, the 1-st judge gave the lowest grade (10 points), which is also invalidated.
Thus, the average is \displaystyle\frac{20+50+30}{3}=33.333\cdots.

Note that the output will be considered correct if the absolute or relative error from the true value is at most 10^{-5}.

Sample Input 2

2
3 3 3 4 5 6 7 8 99 100

Sample Output 2

5.500000000000000

Since N=2, the grades given by the two judges who gave the highest grades, and two with the lowest, are invalidated.
The 10-th and 9-th judges gave the highest grades (100 and 99 points, respectively), which are invalidated.
Three judges, the 1-st, 2-nd, and 3-rd, gave the lowest grade (3 points), so two of them are invalidated.
Thus, the average is \displaystyle\frac{3+4+5+6+7+8}{6}=5.5.

Note that the choice of the two invalidated judges from the three with the lowest grades does not affect the answer.

Problem Statement

Takahashi is on a two-dimensional plane. Starting from the origin, he made N moves.

The N moves are represented by a string of length N as described below:

• Takahashi's coordinates after the i-th move are:

  • (x+1,y) if the i-th character of S is R;
  • (x-1,y) if the i-th character of S is L;
  • (x,y+1) if the i-th character of S is U; and
  • (x,y-1) if the i-th character of S is D,

  where (x,y) is his coordinates before the move.

Determine if Takahashi visited the same coordinates multiple times in the course of the N moves (including the starting and ending points).

Constraints

• 1 \leq N \leq 2\times 10^5
• N is an integer.
• S is a string of length N consisting of R, L, U, and D.

Sample Input 1

5
RLURU

Sample Output 1

Yes

Takahashi's coordinates change as follows: (0,0)\to (1,0)\to (0,0)\to (0,1)\to (1,1)\to (1,2).

Sample Input 2

20
URDDLLUUURRRDDDDLLLL

Sample Output 2

No

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

There is a length-N sequence A=(A_1,\ldots,A_N) that is a permutation of 1,\ldots,N.

While you do not know A, you know that A_{X_i}<A_{Y_i} for M pairs of integers (X_i,Y_i).

Can A be uniquely determined? If it is possible, find A.

Constraints

• 2 \leq N \leq 2\times 10^5
• 1 \leq M \leq 2\times 10^5
• 1\leq X_i,Y_i \leq N
• All values in the input are integers.
• There is an A consistent with the input.

Sample Input 1

3 2
3 1
2 3

Sample Output 1

Yes
3 1 2

We can uniquely determine that A=(3,1,2).

Sample Input 2

3 2
3 1
3 2

Sample Output 2

No

Two sequences (2,3,1) and (3,2,1) can be A.

Sample Input 3

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

Sample Output 3

Yes
1 2 3 4

Problem Statement

There are N cities numbered city 1, city 2, \ldots, and city N.
There are also one-way teleporters that send you to different cities. Whether a teleporter can send you directly from city i (1\leq i\leq N) to another is represented by a length-M string S_i consisting of 0 and 1. Specifically, for 1\leq j\leq N,

• if 1\leq j-i\leq M and the (j-i)-th character of S_i is 1, then a teleporter can send you directly from city i to city j;
• otherwise, it cannot send you directly from city i to city j.

Solve the following problem for k=2,3,\ldots, N-1:

Can you travel from city 1 to city N without visiting city k by repeatedly using a teleporter? If you can, print the minimum number of times you need to use a teleporter; otherwise, print -1.

Constraints

• 3 \leq N \leq 10^5
• 1\leq M\leq 10
• M<N
• S_i is a string of length M consisting of 0 and 1.
• If i+j>N, then the j-th character of S_i is 0.
• N and M are integers.

Sample Input 1

5 2
11
01
11
10
00

Sample Output 1

2 3 2

A teleporter sends you

• from city 1 to cities 2 and 3;
• from city 2 to city 4;
• from city 3 to cities 4 and 5;
• from city 4 to city 5; and
• from city 5 to nowhere.

Therefore, there are three paths to travel from city 1 to city 5:

• path 1 : city 1 \to city 2 \to city 4 \to city 5;
• path 2 : city 1 \to city 3 \to city 4 \to city 5; and
• path 3 : city 1 \to city 3 \to city 5.

Among these paths,

• two paths, path 2 and path 3, do not visit city 2. Among them, path 3 requires the minimum number of teleporter uses (twice).
• Path 1 is the only path without city 3. It requires using a teleporter three times.
• Path 3 is the only path without city 4. It requires using a teleporter twice.

Thus, 2, 3, and 2, separated by spaces, should be printed.

Sample Input 2

6 3
101
001
101
000
100
000

Sample Output 2

-1 3 3 -1

The only path from city 1 to city 6 is city 1 \to city 2 \to city 5 \to city 6.
For k=2,5, there is no way to travel from city 1 to city 6 without visiting city k.
For k=3,4, the path above satisfies the condition; it requires using a teleporter three times.

Thus, -1, 3, 3, and -1, separated by spaces, should be printed.

Note that a teleporter is one-way; a teleporter can send you from city 3 to city 4, but not from city 4 to city 3,
so the following path, for example, is invalid: city 1 \to city 4 \to city 3 \to city 6.

Problem Statement

There are length-N sequences A=(A_0,A_1,\ldots,A_{N-1}) and B=(B_0,B_1,\ldots,B_{N-1}).
Takahashi may perform the following operation on A any number of times (possibly zero):

• apply a left cyclic shift to the sequence A. In other words, replace A with A' defined by A'_i=A_{(i+1)\% N}, where x\% N denotes the remainder when x is divided by N.

Takahashi's objective is to maximize \displaystyle\sum_{i=0}^{N-1} (A_i|B_i), where x|y denotes the bitwise logical sum (bitwise OR) of x and y.

Find the maximum possible \displaystyle\sum_{i=0}^{N-1} (A_i|B_i).

0110 | 0101 = 0111

Constraints

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

Sample Input 1

3
0 1 3
0 2 3

Sample Output 1

8

If Takahashi does not perform the operation, A remains (0,1,3), and we have \displaystyle\sum_{i=0}^{N-1} (A_i|B_i)=(0|0)+(1|2)+(3|3)=0+3+3=6;
if he performs the operation once, making A=(1,3,0), we have \displaystyle\sum_{i=0}^{N-1} (A_i|B_i)=(1|0)+(3|2)+(0|3)=1+3+3=7; and
if he performs the operation twice, making A=(3,0,1), we have \displaystyle\sum_{i=0}^{N-1} (A_i|B_i)=(3|0)+(0|2)+(1|3)=3+2+3=8.
If he performs the operation three or more times, A becomes one of the sequences above, so the maximum possible \displaystyle\sum_{i=0}^{N-1} (A_i|B_i) is 8, which should be printed.

Sample Input 2

5
1 6 1 4 3
0 6 4 0 1

Sample Output 2

23

The value is maximized if he performs the operation three times, making A=(4,3,1,6,1),
where \displaystyle\sum_{i=0}^{N-1} (A_i|B_i)=(4|0)+(3|6)+(1|4)+(6|0)+(1|1)=4+7+5+6+1=23.

Problem Statement

You are given a tree T with N vertices. The i-th edge connects vertices A_i and B_i.

Construct an N-vertex rooted tree R that satisfies the following conditions.

• For all integer pairs (x,y) such that 1 \leq x < y \leq N,
  • if the lowest common ancestor in R of vertices x and y is vertex z, then vertex z in T is on the simple path between vertices x and y.
• In R, for all vertices v except for the root, the number of vertices of the subtree rooted at v, multiplied by 2, does not exceed the number of vertices of the subtree rooted at the parent of v.

We can prove that such a rooted tree always exists.

Constraints

• 1 \leq N \leq 10^5
• 1\leq A_i,B_i \leq N
• All values in the input are integers.
• The given graph is a tree.

Sample Input 1

4
1 2
2 3
3 4

Sample Output 1

2 -1 4 2

For example, the lowest common ancestor in R of vertices 1 and 3 is vertex 2; in T, vertex 2 is on the simple path between vertices 1 and 3.
Also, for example, in R, the subtree rooted at vertex 4 has two vertices, and the number multiplied by two does not exceed the number of vertices of the subtree rooted at vertex 2, which has 4 vertices.

Sample Input 2

5
1 2
1 3
1 4
1 5

Sample Output 2

-1 1 1 1 1