Problem Statement

You are given a string S consisting of lowercase English letters. The length of S is between 3 and 100, inclusive.

All characters but one of S are the same.

Find x such that the x-th character of S differs from all other characters.

Constraints

• S is a string of length between 3 and 100, inclusive, consisting of two different lowercase English letters.
• All characters but one of S are the same.

Sample Input 1

yay

Sample Output 1

2

The second character of yay differs from the first and third characters.

Sample Input 2

egg

Sample Output 2

1

Sample Input 3

zzzzzwz

Sample Output 3

6

Problem Statement

There are N people standing in a line. The person standing at the i-th position from the front is person P_i.

Process Q queries. The i-th query is as follows:

• You are given integers A_i and B_i. Between person A_i and person B_i, print the person number of the person standing further to the front.

Constraints

• All inputs are integers.
• 1 \leq N \leq 100
• 1 \leq P_i \leq N
• P_i \neq P_j\ (i \neq j)
• 1 \leq Q \leq 100
• 1 \leq A_i < B_i \leq N

Sample Input 1

3
2 1 3
3
2 3
1 2
1 3

Sample Output 1

2
2
1

In the first query, person 2 is at the first position from the front, and person 3 is at the third position, so person 2 is further to the front.

In the second query, person 1 is at the second position from the front, and person 2 is at the first position, so person 2 is further to the front.

In the third query, person 1 is at the second position from the front, and person 3 is at the third position, so person 1 is further to the front.

Sample Input 2

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

Sample Output 2

3
2
3
3
3
2
3
3
7
1
2
3
3

Problem Statement

You are given a string S of length N consisting of lowercase English letters.

You will perform an operation Q times on the string S. The i-th operation (1\leq i\leq Q) is represented by a pair of characters (c _ i,d _ i), which corresponds to the following operation:

• Replace all occurrences of the character c _ i in S with the character d _ i.

Print the string S after all operations are completed.

Constraints

• 1\leq N\leq2\times10^5
• S is a string of length N consisting of lowercase English letters.
• 1\leq Q\leq2\times10^5
• c _ i and d _ i are lowercase English letters (1\leq i\leq Q).
• N and Q are integers.

Sample Input 1

7
atcoder
4
r a
t e
d v
a r

Sample Output 1

recover

S changes as follows: atcoder → atcodea → aecodea → aecovea → recover. For example, in the fourth operation, all occurrences of a in S={}aecovea (the first and seventh characters) are replaced with r, resulting in S={}recover.

After all operations are completed, S={}recover, so print recover.

Sample Input 2

3
abc
4
a a
s k
n n
z b

Sample Output 2

abc

There may be operations where c _ i=d _ i or S does not contain c _ i.

Sample Input 3

34
supercalifragilisticexpialidocious
20
g c
l g
g m
c m
r o
s e
a a
o f
f s
e t
t l
d v
p k
v h
x i
h n
n j
i r
s i
u a

Sample Output 3

laklimamriiamrmrllrmlrkramrjimrial

Problem Statement

You are given a sequence of non-negative integers A=(A_1,\ldots,A_N) of length N. Find the number of pairs of integers (i,j) that satisfy both of the following conditions:

• 1\leq i < j\leq N
• A_i A_j is a square number.

Here, a non-negative integer a is called a square number when it can be expressed as a=d^2 using some non-negative integer d.

Constraints

• All inputs are integers.
• 2\leq N\leq 2\times 10^5
• 0\leq A_i\leq 2\times 10^5

Sample Input 1

5
0 3 2 8 12

Sample Output 1

6

Six pairs of integers, (i,j)=(1,2),(1,3),(1,4),(1,5),(2,5),(3,4), satisfy the conditions.

For example, A_2A_5=36, and 36 is a square number, so the pair (i,j)=(2,5) satisfies the conditions.

Sample Input 2

8
2 2 4 6 3 100 100 25

Sample Output 2

7

Problem Statement

In the country of AtCoder, there are N stations: station 1, station 2, \ldots, station N.

You are given M pieces of information about trains in the country. The i-th piece of information (1\leq i\leq M) is represented by a tuple of six positive integers (l _ i,d _ i,k _ i,c _ i,A _ i,B _ i), which corresponds to the following information:

• For each t=l _ i,l _ i+d _ i,l _ i+2d _ i,\ldots,l _ i+(k _ i-1)d _ i, there is a train as follows:
  • The train departs from station A _ i at time t and arrives at station B _ i at time t+c _ i.

No trains exist other than those described by this information, and it is impossible to move from one station to another by any means other than by train.
Also, assume that the time required for transfers is negligible.

Let f(S) be the latest time at which one can arrive at station N from station S.
More precisely, f(S) is defined as the maximum value of t for which there is a sequence of tuples of four integers \big((t _ i,c _ i,A _ i,B _ i)\big) _ {i=1,2,\ldots,k} that satisfies all of the following conditions:

• t\leq t _ 1
• A _ 1=S,B _ k=N
• B _ i=A _ {i+1} for all 1\leq i\lt k,
• For all 1\leq i\leq k, there is a train that departs from station A _ i at time t _ i and arrives at station B _ i at time t _ i+c _ i.
• t _ i+c _ i\leq t _ {i+1} for all 1\leq i\lt k.

If no such t exists, set f(S)=-\infty.

Find f(1),f(2),\ldots,f(N-1).

Constraints

• 2\leq N\leq2\times10 ^ 5
• 1\leq M\leq2\times10 ^ 5
• 1\leq l _ i,d _ i,k _ i,c _ i\leq10 ^ 9\ (1\leq i\leq M)
• 1\leq A _ i,B _ i\leq N\ (1\leq i\leq M)
• A _ i\neq B _ i\ (1\leq i\leq M)
• All input values are integers.

Sample Input 1

6 7
10 5 10 3 1 3
13 5 10 2 3 4
15 5 10 7 4 6
3 10 2 4 2 5
7 10 2 3 5 6
5 3 18 2 2 3
6 3 20 4 2 1

Sample Output 1

55
56
58
60
17

The following diagram shows the trains running in the country (information about arrival and departure times is omitted).

Consider the latest time at which one can arrive at station 6 from station 2. As shown in the following diagram, one can arrive at station 6 by departing from station 2 at time 56 and moving as station 2\rightarrow station 3\rightarrow station 4\rightarrow station 6.

It is impossible to depart from station 2 after time 56 and arrive at station 6, so f(2)=56.

Sample Input 2

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

Sample Output 2

1000000000000000000
Unreachable
1
Unreachable

There is a train that departs from station 1 at time 10 ^ {18} and arrives at station 5 at time 10 ^ {18}+10 ^ 9. There are no trains departing from station 1 after that time, so f(1)=10 ^ {18}. As seen here, the answer may not fit within a 32\operatorname{bit} integer.

Also, both the second and third pieces of information guarantee that there is a train that departs from station 2 at time 14 and arrives at station 3 at time 20. As seen here, some trains may appear in multiple pieces of information.

Sample Input 3

16 20
4018 9698 2850 3026 8 11
2310 7571 7732 1862 13 14
2440 2121 20 1849 11 16
2560 5115 190 3655 5 16
1936 6664 39 8822 4 16
7597 8325 20 7576 12 5
5396 1088 540 7765 15 1
3226 88 6988 2504 13 5
1838 7490 63 4098 8 3
1456 5042 4 2815 14 7
3762 6803 5054 6994 10 9
9526 6001 61 8025 7 8
5176 6747 107 3403 1 5
2014 5533 2031 8127 8 11
8102 5878 58 9548 9 10
3788 174 3088 5950 3 13
7778 5389 100 9003 10 15
556 9425 9458 109 3 11
5725 7937 10 3282 2 9
6951 7211 8590 1994 15 12

Sample Output 3

720358
77158
540926
255168
969295
Unreachable
369586
466218
343148
541289
42739
165772
618082
16582
591828

Problem Statement

You will play a game against a dealer. The game uses a D-sided die (dice) that shows an integer from 1 to D with equal probability, and two variables x and y initialized to 0. The game proceeds as follows:

• You may perform the following operation any number of times: roll the die and add the result to x. You can choose whether to continue rolling or not after each roll.

• Then, the dealer will repeat the following operation as long as y < L: roll the die and add the result to y.

• If x > N, you lose. Otherwise, you win if y > N or x > y and lose if neither is satisfied.

Determine the probability of your winning when you act in a way that maximizes the probability of winning.

Constraints

• All inputs are integers.
• 1 \leq L \leq N \leq 2 \times 10^5
• 1 \leq D \leq N

Sample Input 1

3 2 2

Sample Output 1

0.468750000000000

It can be proved that the optimal strategy is to continue rolling as long as x is not greater than 2.

Sample Input 2

200000 200000 200000

Sample Output 2

0.999986408692793

Problem Statement

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

Process Q operations in order. There are three types of operations:

• A type-1 operation is represented by a triple of integers (l,r,x), which corresponds to replacing A_i with \max\lbrace A_i,x\rbrace for each i=l,l+1,\ldots,r.
• A type-2 operation is represented by an integer i, which corresponds to canceling the i-th operation (it is guaranteed that the i-th operation is of type 1 and has not already been canceled). The new sequence A can be obtained by performing all type-1 operations that have not been canceled, starting from the initial state.
• A type-3 operation is represented by an integer i, which corresponds to printing the current value of A_i.

Constraints

• 1\leq N\leq2\times10^5
• 1\leq A_i\leq10^9\ (1\leq i\leq N)
• 1\leq Q\leq2\times10^5
• In a type-1 operation, 1\leq l\leq r\leq N and 1\leq x\leq10^9.
• In a type-2 operation, i is not greater than the number of operations given before, and 1\leq i.
• In a type-2 operation, the i-th operation is of type 1.
• In type-2 operations, the same i does not appear multiple times.
• In a type-3 operation, 1\leq i\leq N.
• All input values are integers.

Sample Input 1

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

Sample Output 1

2
1
8
4
4
8
4
9
9
2
9
9

Initially, the sequence A is (2,7,1,8,2,8).

For the 1-st, 2-nd, 3-rd operations, print the values of A_1, A_3, A_4, which are 2,1,8, respectively.

The 4-th operation replaces the values of A_1, A_2, A_3, A_4, A_5 with \max\lbrace A_i,4\rbrace. Just after this operation, A is (4,7,4,8,4,8).

For the 5-th, 6-th, 7-th operations, print the values of A_1, A_3, A_4 at this point, which are 4,4,8, respectively.

The 8-th operation replaces the values of A_3, A_4, A_5, A_6 with \max\lbrace A_i,9\rbrace. Just after this operation, A is (4,7,9,9,9,9).

For the 9-th, 10-th, 11-th operations, print the values of A_1, A_3, A_4 at this point, which are 4,9,9, respectively.

The 12-th operation cancels the 4-th operation. Just after this operation, A is (2,7,9,9,9,9).

For the 13-th, 14-th, 15-th operations, print the values of A_1, A_3, A_4 at this point, which are 2,9,9, respectively.

Sample Input 2

24
721 78 541 256 970 478 370 467 344 542 43 166 619 17 592 222 983 729 338 747 62 452 815 838
35
3 10
3 8
3 8
3 13
3 9
1 1 17 251
3 3
3 19
3 13
3 22
3 1
3 15
3 18
3 10
3 15
1 16 19 883
1 8 23 212
3 5
3 13
2 6
3 15
1 5 18 914
2 17
3 20
1 23 23 56
3 13
2 25
3 13
3 13
3 10
2 16
1 17 22 308
3 19
3 17
3 7

Sample Output 2

542
467
467
619
344
541
338
619
452
721
592
729
542
592
970
619
592
747
914
914
914
914
338
983
914