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

Given integers a, b, and c, determine if b is the median of these integers.

Constraints

• 1 \leq a, b, c \leq 100
• All values in input are integers.

Sample Input 1

5 3 2

Sample Output 1

Yes

The given integers are 2, 3, 5 when sorted in ascending order, of which b is the median.

Sample Input 2

2 5 3

Sample Output 2

No

b is not the median of the given integers.

Sample Input 3

100 100 100

Sample Output 3

Yes

Problem Statement

You are given an integer N and a sequence A=(A _ 1,A _ 2,\ldots,A _ N) of length N.

Given Q queries, process them in the given order. Each query is of one of the following two kinds:

• 1 k x : set the value A _ k to x.
• 2 k : print the value A _ k.

Constraints

• 1 \leq N \leq 10 ^ 5
• 1 \leq Q \leq 10 ^ 5
• 0 \leq A _ i \leq 10 ^ 9\ (1\leq i\leq N)
• 1\leq k\leq N for all queries.
• 0\leq x\leq 10 ^ 9 for all queries of the first kind.
• There is at least one query of the second kind.
• All values in the input are integers.

Sample Input 1

3
1 3 5
7
2 2
2 3
1 3 0
2 3
1 2 8
2 2
2 1

Sample Output 1

3
5
0
8
1

Initially, A=(1,3,5).

• For the 1-st query, A=(1,3,5), where A _ 2=3, so 3 should be printed.
• For the 2-nd query, A=(1,3,5), where A _ 3=5, so 5 should be printed.
• The 3-rd query sets the value A _ 3 to 0, making A=(1,3,0).
• For the 4-th query, A=(1,3,0), where A _ 3=0, so 0 should be printed.
• The 5-th query sets the value A _ 2 to 8, making A=(1,8,0).
• For the 6-th query, A=(1,8,0), where A _ 2=8, so 8 should be printed.
• For the 7-th query, A=(1,8,0), where A _ 1=1, so 1 should be printed.

Sample Input 2

5
22 2 16 7 30
10
1 4 0
1 5 0
2 2
2 3
2 4
2 5
1 4 100
1 5 100
2 3
2 4

Sample Output 2

2
16
0
0
16
100

Sample Input 3

7
478 369 466 343 541 42 165
20
2 1
1 7 729
1 6 61
1 6 838
1 3 319
1 4 317
2 4
1 1 673
1 3 176
1 5 250
1 1 468
2 6
1 7 478
1 5 595
2 6
1 6 599
1 6 505
2 3
2 5
2 1

Sample Output 3

478
317
838
838
176
595
468

Problem Statement

AtCoder Kingdom uses a calendar whose year has N months. Month i (1\leq i\leq N) has D _ i days, from day 1 of month i to day D _ i of month i.

How many days in a year of AtCoder have "repdigits" dates?

Here, day j of month i (1\leq i\leq N,1\leq j\leq D _ i) is said to have a repdigit date if and only if all digits in the decimal notations of i and j are the same.

Constraints

• 1\leq N\leq100
• 1\leq D _ i\leq100\ (1\leq i\leq N)
• All input values are integers.

Sample Input 1

12
31 29 31 30 31 30 31 31 30 31 30 31

Sample Output 1

13

In AtCoder Kingdom, the days that have repdigit dates are January 1, January 11, February 2, February 22, March 3, April 4, May 5, June 6, July 7, August 8, September 9, November 1, and November 11, for a total of 13 days.

Sample Input 2

10
10 1 2 3 4 5 6 7 8 100

Sample Output 2

1

In AtCoder Kingdom, only January 1 has a repdigit date.

Sample Input 3

30
73 8 55 26 97 48 37 47 35 55 5 17 62 2 60 23 99 73 34 75 7 46 82 84 29 41 32 31 52 32

Sample Output 3

15

Problem Statement

You are given N strings S_1,S_2,\dots,S_N consisting of lowercase English alphabets.

Consider choosing some number of strings from S_1,S_2,\dots,S_N.

Find the maximum number of distinct alphabets that satisfy the following condition: "the alphabet is contained in exactly K of the chosen strings."

Constraints

• 1 \le N \le 15
• 1 \le K \le N
• N and K are integers.
• S_i is a non-empty string consisting of lowercase English alphabets.
• For each integer i such that 1 \le i \le N, S_i does not contain two or more same alphabets.
• If i \neq j, then S_i \neq S_j.

Sample Input 1

4 2
abi
aef
bc
acg

Sample Output 1

3

When S_1,S_3, and S_4 are chosen, a,b, and c occur in exactly two of the strings.

There is no way to choose strings so that 4 or more alphabets occur in exactly 2 of the strings, so the answer is 3.

Sample Input 2

2 2
a
b

Sample Output 2

0

You cannot choose the same string more than once.

Sample Input 3

5 2
abpqxyz
az
pq
bc
cy

Sample Output 3

7

Problem Statement

There are N creatures standing in a circle, called Snuke 1, 2, ..., N in counter-clockwise order.

When Snuke i (1 \leq i \leq N) receives a gem at time t, S_i units of time later, it will hand that gem to Snuke i+1 at time t+S_i. Here, Snuke N+1 is Snuke 1.

Additionally, Takahashi will hand a gem to Snuke i at time T_i.

For each i (1 \leq i \leq N), find the time when Snuke i receives a gem for the first time. Assume that it takes a negligible time to hand a gem.

Constraints

• 1 \leq N \leq 200000
• 1 \leq S_i,T_i \leq 10^9
• All values in input are integers.

Sample Input 1

3
4 1 5
3 10 100

Sample Output 1

3
7
8

We will list the three Snuke's and Takahashi's actions up to time 13 in chronological order.

Time 3: Takahashi hands a gem to Snuke 1.

Time 7: Snuke 1 hands a gem to Snuke 2.

Time 8: Snuke 2 hands a gem to Snuke 3.

Time 10: Takahashi hands a gem to Snuke 2.

Time 11: Snuke 2 hands a gem to Snuke 3.

Time 13: Snuke 3 hands a gem to Snuke 1.

After that, they will continue handing gems, though it will be irrelevant to the answer.

Sample Input 2

4
100 100 100 100
1 1 1 1

Sample Output 2

1
1
1
1

Note that the values S_i and T_i may not be distinct.

Sample Input 3

4
1 2 3 4
1 2 4 7

Sample Output 3

1
2
4
7

Note that a Snuke may perform multiple transactions simultaneously. Particularly, a Snuke may receive gems simultaneously from Takahashi and another Snuke.

Sample Input 4

8
84 87 78 16 94 36 87 93
50 22 63 28 91 60 64 27

Sample Output 4

50
22
63
28
44
60
64
27

Problem Statement

Your computer has a keyboard with three keys: 'a' key, Shift key, and Caps Lock key. The Caps Lock key has a light on it. Initially, the light on the Caps Lock key is off, and the screen shows an empty string.

You can do the following three actions any number of times in any order:

• Spend X milliseconds to press only the 'a' key. If the light on the Caps Lock key is off, a is appended to the string on the screen; if it is on, A is.
• Spend Y milliseconds to press the 'a' key and Shift key simultaneously. If the light on the Caps Lock key is off, A is appended to the string on the screen; if it is on, a is.
• Spend Z milliseconds to press the Caps Lock key. If the light on the Caps Lock key is off, it turns on; if it is on, it turns off.

Given a string S consisting of A and a, determine at least how many milliseconds you need to spend to make the string shown on the screen equal to S.

Constraints

• 1 \leq X,Y,Z \leq 10^9
• X, Y, and Z are integers.
• 1 \leq |S| \leq 3 \times 10^5
• S is a string consisting of A and a.

Sample Input 1

1 3 3
AAaA

Sample Output 1

9

The following sequence of actions makes the string on the screen equal to AAaA in 9 milliseconds, which is the shortest possible.

• Spend Z(=3) milliseconds to press the CapsLock key. The light on the Caps Lock key turns on.
• Spend X(=1) milliseconds to press the 'a' key. A is appended to the string on the screen.
• Spend X(=1) milliseconds to press the 'a' key. A is appended to the string on the screen.
• Spend Y(=3) milliseconds to press the Shift key and 'a' key simultaneously. a is appended to the string on the screen.
• Spend X(=1) milliseconds to press the 'a' key. A is appended to the string on the screen.

Sample Input 2

1 1 100
aAaAaA

Sample Output 2

6

Sample Input 3

1 2 4
aaAaAaaAAAAaAaaAaAAaaaAAAAA

Sample Output 3

40

Problem Statement

There are 2N points placed at equal intervals on a circle, numbered 1 to 2N in a clockwise direction starting from a certain point.

There are also N chords on the circle, with the i-th chord connecting points A_i and B_i. It is guaranteed that all the values A_1,\dots,A_N,B_1,\dots,B_N are distinct.

Determine whether there is an intersection between the chords.

Constraints

• 2\leq N \leq 2\times 10^5
• 1\leq A_i,B_i \leq 2N
• A_1,\dots,A_N,B_1,\dots,B_N are all distinct
• All input values are integers

Sample Input 1

3
1 3
4 2
5 6

Sample Output 1

Yes

As shown in the figure, chord 1 (the line segment connecting points 1 and 3) and chord 2 (the line segment connecting points 4 and 2) intersect, so print Yes.

Sample Input 2

3
6 1
4 3
2 5

Sample Output 2

No

As shown in the figure, there is no intersection between the chords, so print No.

Sample Input 3

4
2 4
3 7
8 6
5 1

Sample Output 3

Yes

Problem Statement

You are given a directed graph with N vertices and M edges. The vertices are numbered 1 through N, and the edges are numbered 1 through M. Edge i (1 \leq i \leq M) goes from Vertex s_i to Vertex t_i and has a length of 1.

For each i (1 \leq i \leq M), find the shortest distance from Vertex 1 to Vertex N when all edges except Edge i are passable, or print -1 if Vertex N is unreachable from Vertex 1.

Constraints

• 2 \leq N \leq 400
• 1 \leq M \leq N(N-1)
• 1 \leq s_i,t_i \leq N
• s_i \neq t_i
• (s_i,t_i) \neq (s_j,t_j) (i \neq j)
• All values in input are integers.

Sample Input 1

3 3
1 2
1 3
2 3

Sample Output 1

1
2
1

Sample Input 2

4 4
1 2
2 3
2 4
3 4

Sample Output 2

-1
2
3
2

Vertex N is unreachable from Vertex 1 when all edges except Edge 1 are passable, so the corresponding line contains -1.

Sample Input 3

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

Sample Output 3

1
1
3
1
1
1
1
1
1
1

Sample Input 4

4 1
1 2

Sample Output 4

-1