Problem Statement

You are given N integers A _ 1,A _ 2,\ldots,A _ N.

If their values are all equal, print Yes; otherwise, print No.

Constraints

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

Sample Input 1

3
3 2 4

Sample Output 1

No

We have A _ 1\neq A _ 2, so you should print No.

Sample Input 2

4
3 3 3 3

Sample Output 2

Yes

We have A _ 1=A _ 2=A _ 3=A _ 4, so you should print Yes.

Sample Input 3

10
73 8 55 26 97 48 37 47 35 55

Sample Output 3

No

Problem Statement

You are given a positive integer N. If there are integers x and y such that N=2^x3^y, print Yes; otherwise, print No.

Constraints

• 1\leq N\leq10^{18}
• N is an integer.

Sample Input 1

324

Sample Output 1

Yes

For x=2,y=4, we have 2^x3^y=2^23^4=4\times81=324, so the condition is satisfied. Thus, you should print Yes.

Sample Input 2

5

Sample Output 2

No

There are no integers x and y such that 2^x3^y=5. Thus, you should print No.

Sample Input 3

32

Sample Output 3

Yes

For x=5,y=0, we have 2^x3^y=32\times1=32, so you should print Yes.

Sample Input 4

37748736

Sample Output 4

Yes

Problem Statement

Takahashi sent a string T consisting of lowercase English letters to Aoki. As a result, Aoki received a string T' consisting of lowercase English letters.

T' may have been altered from T. Specifically, exactly one of the following four conditions is known to hold.

• T' is equal to T.
• T' is a string obtained by inserting one lowercase English letter at one position (possibly the beginning and end) in T.
• T' is a string obtained by deleting one character from T.
• T' is a string obtained by changing one character in T to another lowercase English letter.

You are given the string T' received by Aoki and N strings S_1, S_2, \ldots, S_N consisting of lowercase English letters. Find all the strings among S_1, S_2, \ldots, S_N that could equal the string T sent by Takahashi.

Constraints

• N is an integer.
• 1 \leq N \leq 5 \times 10^5
• S_i and T' are strings of length between 1 and 5 \times 10^5, inclusive, consisting of lowercase English letters.
• The total length of S_1, S_2, \ldots, S_N is at most 5 \times 10^5.

Sample Input 1

5 ababc
ababc
babc
abacbc
abdbc
abbac

Sample Output 1

4
1 2 3 4

Among S_1, S_2, \ldots, S_5, the strings that could be equal to T are S_1, S_2, S_3, S_4, as explained below.

• S_1 could be equal to T, because T' = ababc is equal to S_1 = ababc.
• S_2 could be equal to T, because T' = ababc is obtained by inserting the letter a at the beginning of S_2 = babc.
• S_3 could be equal to T, because T' = ababc is obtained by deleting the fourth character c from S_3 = abacbc.
• S_4 could be equal to T, because T' = ababc is obtained by changing the third character d in S_4 = abdbc to b.
• S_5 could not be equal to T, because if we take S_5 = abbac as T, then T' = ababc does not satisfy any of the four conditions in the problem statement.

Sample Input 2

1 aoki
takahashi

Sample Output 2

0

Sample Input 3

9 atcoder
atoder
atcode
athqcoder
atcoder
tacoder
jttcoder
atoder
atceoder
atcoer

Sample Output 3

6
1 2 4 7 8 9

Problem Statement

You are given a string S of length N consisting of digits.

Find the number of square numbers that can be obtained by interpreting a permutation of S as a decimal integer.

More formally, solve the following.

Let s _ i be the number corresponding to the i-th digit (1\leq i\leq N) from the beginning of S.

Find the number of square numbers that can be represented as \displaystyle \sum _ {i=1} ^ N s _ {p _ i}10 ^ {N-i} with a permutation P=(p _ 1,p _ 2,\ldots,p _ N) of (1, \dots, N).

Constraints

• 1\leq N\leq 13
• S is a string of length N consisting of digits.
• N is an integer.

Sample Input 1

4
4320

Sample Output 1

2

For P=(4,2,3,1), we have s _ 4\times10 ^ 3+s _ 2\times10 ^ 2+s _ 3\times10 ^ 1+s _ 1=324=18 ^ 2.
For P=(3,2,4,1), we have s _ 3\times10 ^ 3+s _ 2\times10 ^ 2+s _ 4\times10 ^ 1+s _ 1=2304=48 ^ 2.

No other permutations result in square numbers, so you should print 2.

Sample Input 2

3
010

Sample Output 2

2

For P=(1,3,2) or P=(3,1,2), we have \displaystyle\sum _ {i=1} ^ Ns _ {p _ i}10 ^ {N-i}=1=1 ^ 2.
For P=(2,1,3) or P=(2,3,1), we have \displaystyle\sum _ {i=1} ^ Ns _ {p _ i}10 ^ {N-i}=100=10 ^ 2.

No other permutations result in square numbers, so you should print 2. Note that different permutations are not distinguished if they result in the same number.

Sample Input 3

13
8694027811503

Sample Output 3

840

Problem Statement

You are given N strings S_1, S_2, \ldots, S_N consisting of lowercase English letters, and a string T consisting of lowercase English letters.

There are N^2 pairs (i, j) of integers between 1 and N, inclusive. Print the number of pairs among them that satisfy the following condition.

• The concatenation of S_i and S_j in this order contains T as a (not necessarily contiguous) subsequence.

Constraints

• N is an integer.
• 1 \leq N \leq 5 \times 10^5
• S_i and T are strings of length 1 to 5 \times 10^5, inclusive, consisting of lowercase English letters.
• The total length of S_1, S_2, \ldots, S_N is at most 5 \times 10^5.

Sample Input 1

3 bac
abba
bcb
aaca

Sample Output 1

3

The pairs (i, j) that satisfy the condition in the problem statement are (1, 2), (1, 3), (2, 3), as seen below.

• For (i, j) = (1, 2), the concatenation abbabcb of S_1 and S_2 in this order contains bac as a subsequence.
• For (i, j) = (1, 3), the concatenation abbaaaca of S_1 and S_3 in this order contains bac as a subsequence.
• For (i, j) = (2, 3), the concatenation bcbaaca of S_2 and S_3 in this order contains bac as a subsequence.

Sample Input 2

5 xx
x
x
x
x
x

Sample Output 2

25

Sample Input 3

1 y
x

Sample Output 3

0

Sample Input 4

10 ms
mkgn
m
hlms
vmsle
mxsm
nnzdhi
umsavxlb
ffnsybomr
yvmm
naouel

Sample Output 4

68

Problem Statement

There is a directed graph with N vertices and M edges. Each edge has two positive integer values: beauty and cost.

For i = 1, 2, \ldots, M, the i-th edge is directed from vertex u_i to vertex v_i, with beauty b_i and cost c_i. Here, the constraints guarantee that u_i \lt v_i.

Find the maximum value of the following for a path P from vertex 1 to vertex N.

• The total beauty of all edges on P divided by the total cost of all edges on P.

Here, the constraints guarantee that the given graph has at least one path from vertex 1 to vertex N.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq u_i \lt v_i \leq N
• 1 \leq b_i, c_i \leq 10^4
• There is a path from vertex 1 to vertex N.
• All input values are integers.

Sample Input 1

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

Sample Output 1

0.7500000000000000

For the path P that passes through the 2-nd, 6-th, and 7-th edges in this order and visits vertices 1 \rightarrow 3 \rightarrow 4 \rightarrow 5, the total beauty of all edges on P divided by the total cost of all edges on P is (b_2 + b_6 + b_7) / (c_2 + c_6 + c_7) = (9 + 4 + 2) / (5 + 8 + 7) = 15 / 20 = 0.75, and this is the maximum possible value.

Sample Input 2

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

Sample Output 2

3.0000000000000000

Sample Input 3

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

Sample Output 3

1.8333333333333333

Problem Statement

Takahashi has a sequence of length N: A=(A _ 1,A _ 2,\ldots,A _ N). A is a permutation of (1,2,\ldots,N).

He is going to perform Q operations to create 1+Q sequences. He lets A be the sequence numbered 0, and then begins the series of operations. The i-th operation (1\leq i\leq Q) is represented by a triple of integers (t _ i,s _ i,x _ i) and corresponds to the following operation (see also the explanations in Sample Input/Output).

• When t _ i=1, he removes the elements following the x _ i-th element from the sequence numbered s _ i (0\leq s _ i\lt i), and creates a new sequence numbered i with the removed elements, keeping their order.
• When t _ i=2, he removes the elements greater than x _ i from the sequence numbered s _ i (0\leq s _ i\lt i), and creates a new sequence numbered i with the removed elements, keeping their order.

For a sequence X of length L, every element of X is among "the elements following the 0-th element." Also, for any l such that L\leq l, no element of X is among "the elements following the l-th element."

For i=1,2,\ldots,Q, find the length of the sequence numbered i immediately after the i-th operation.

Constraints

• 1\leq N\leq2\times10^5
• 1\leq A _ i\leq N\ (1\leq i\leq N)
• A _ i\neq A _ j\ (1\leq i\lt j\leq N)
• 1\leq Q\leq2\times10^5
• t _ i=1,2\ (1\leq i\leq Q)
• 0\leq s _ i\lt i\ (1\leq i\leq Q)
• 0\leq x _ i\leq N\ (1\leq i\leq Q)
• All input values are integers.

Sample Input 1

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

Sample Output 1

6
4
2
3
1

Initially, Takahashi has a sequence A=(1,8,7,4,5,6,3,2,9,10) of length 10. He lets A=(1,8,7,4,5,6,3,2,9,10) be the sequence numbered 0, and then begins the series of operations.

In the first operation, he removes elements greater than 4 from the sequence numbered 0, namely 8,7,5,6,9,10, and creates a new sequence numbered 1 with these elements. After this operation, the sequences numbered 0 and 1 are (1,4,3,2) and (8,7,5,6,9,10), respectively.

In the second operation, he removes the elements following the 2-nd element from the sequence numbered 1, namely 5,6,9,10, and creates a new sequence numbered 2 with these elements. After this operation, the sequences numbered 0, 1, and 2 are (1,4,3,2), (8,7), and (5,6,9,10), respectively.

For the third and subsequent operations, the sequences numbered 0,1,2,\ldots,i after the i-th operation are as follows:

• (1,2),(8,7),(5,6,9,10),(4,3)
• (1,2),(8,7),(5),(4,3),(6,9,10)
• (1),(8,7),(5),(4,3),(6,9,10),(2)

The length of the sequence numbered i after the i-th operation for i=1,2,\ldots,5 is 6,4,2,3,1. Print each of these in its own line.

Sample Input 2

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

Sample Output 2

8
8
8
0
0

The operations may create empty sequences.

Sample Input 3

30
20 6 13 11 29 30 9 10 16 5 8 25 1 19 12 18 7 2 4 27 3 22 23 24 28 21 14 26 15 17
10
1 0 22
1 0 21
2 0 15
1 0 9
1 3 6
2 3 18
1 6 2
1 0 1
2 5 20
2 7 26

Sample Output 3

8
1
8
4
2
5
3
8
1
1