Problem Statement

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

Determine whether there is a place in A where the same element appears three or more times in a row.

More formally, determine whether there exists an integer i with 1 \le i \le N-2 such that A_i = A_{i+1} = A_{i+2}.

Constraints

• 3 \le N \le 100
• 1 \le A_i \le 100
• All input values are integers.

Sample Input 1

5
1 4 4 4 2

Sample Output 1

Yes

We have A=(1,4,4,4,2). There is a place where 4 appears three times in a row, so print Yes.

Sample Input 2

6
2 4 4 2 2 4

Sample Output 2

No

We have A=(2,4,4,2,2,4). There is no place where the same element appears three or more times in a row, so print No.

Sample Input 3

8
1 4 2 5 7 7 7 2

Sample Output 3

Yes

Sample Input 4

10
1 2 3 4 5 6 7 8 9 10

Sample Output 4

No

Sample Input 5

13
1 1 1 1 1 1 1 1 1 1 1 1 1

Sample Output 5

Yes

Problem Statement

Takahashi has N items and one bag.

The size of the i-th (1\le i\le N) item is A_i, and the size of the bag is M.

If and only if the total size of the items he is trying to put in the bag is at most M, he can put all those items in the bag simultaneously.

If he can put all N items in the bag simultaneously, print Yes; otherwise, print No.

Constraints

• 1\le N\le100
• 1\le M\le10000
• 1\le A_i\le100\ (1\le i\le N)
• All input values are integers.

Sample Input 1

5 15
3 1 4 1 5

Sample Output 1

Yes

The total size of the 5 items is 3+1+4+1+5=14. Since this is not greater than the bag size 15, Takahashi can put all items in the bag simultaneously. Thus, print Yes.

Sample Input 2

5 5
3 1 4 1 5

Sample Output 2

No

The total size of the 5 items is 14, which is greater than the bag size 5, so he cannot put all items in the bag simultaneously. Thus, print No.

Sample Input 3

1 10000
100

Sample Output 3

Yes

Problem Statement

Given a positive integer N, find the maximum integer k such that 2^k \le N.

Constraints

• N is an integer satisfying 1 \le N \le 10^{18}.

Sample Input 1

6

Sample Output 1

2

• k=2 satisfies 2^2=4 \le 6.
• For every integer k such that k \ge 3, 2^k > 6 holds.

Therefore, the answer is k=2.

Sample Input 2

1

Sample Output 2

0

Note that 2^0=1.

Sample Input 3

1000000000000000000

Sample Output 3

59

The input value may not fit into a 32-bit integer.

Problem Statement

You are given a sequence of positive integers A=(A_1,A_2,\ldots,A_N) of length N.
Find the number of pairs of integers (l,r) satisfying 1\leq l\leq r\leq N that satisfy the following condition:

For every integer i satisfying l\leq i\leq r, A_i is not a divisor of A_l+A_{l+1}+\cdots+A_r.

Constraints

• 1 \leq N \leq 50
• 1 \leq A_i \leq 1000
• All input values are integers.

Sample Input 1

5
8 6 10 5 7

Sample Output 1

6

We have A=(8,6,10,5,7).

For example, (l,r)=(1,2) satisfies the condition because A_l+A_{l+1}+\cdots+A_r=A_1+A_2=14, and neither A_1=8 nor A_2=6 is a divisor of 14.
On the other hand, (l,r)=(1,3) does not satisfy the condition because A_l+A_{l+1}+\cdots+A_r=A_1+A_2+A_3=24, and A_1=8 is a divisor of 24.

The pairs that satisfy the condition are (l,r)=(1,2), (1,4), (2,3), (2,4), (3,5), (4,5), which is six pairs, so output 6.

Sample Input 2

3
1 1 1

Sample Output 2

0

Problem Statement

There are N versions of a certain OS, numbered 1,2,\dots,N in chronological order.
There are N PCs, and initially the OS version of the i-th PC is i.

Perform Q operations in order. The i-th operation is as follows:

• Upgrade all PCs whose current OS version is X_i or earlier to version Y_i(>X_i). Then, print the number of PCs upgraded in this operation.

Note that for i<Q, the upgrades from the i-th operation are performed before proceeding to the (i+1)-th operation.

Constraints

• All input values are integers.
• 2 \le N \le 10^6
• 1 \le Q \le 2 \times 10^5
• 1 \le X_i < Y_i \le N

Sample Input 1

8 5
2 6
3 5
1 7
5 7
7 8

Sample Output 1

2
1
0
3
7

This input contains five operations.

• Initially, the versions of the eight PCs are 1,2,3,4,5,6,7,8.
• In the first operation, PCs with version 2 or earlier are upgraded to version 6.
  • This operation upgrades two PCs, and the versions of the PCs become 6,6,3,4,5,6,7,8.
• In the second operation, PCs with version 3 or earlier are upgraded to version 5.
  • This operation upgrades one PC, and the versions of the PCs become 6,6,5,4,5,6,7,8.
• In the third operation, PCs with version 1 or earlier are upgraded to version 7.
  • This operation upgrades zero PCs, and the versions of the PCs become 6,6,5,4,5,6,7,8.
• In the fourth operation, PCs with version 5 or earlier are upgraded to version 7.
  • This operation upgrades three PCs, and the versions of the PCs become 6,6,7,7,7,6,7,8.
• In the fifth operation, PCs with version 7 or earlier are upgraded to version 8.
  • This operation upgrades seven PCs, and the versions of the PCs become 8,8,8,8,8,8,8,8.

Problem Statement

The definition of an 11/22 string in this problem is the same as in Problems A and E.

A string T is called an 11/22 string when it satisfies all of the following conditions:

• |T| is odd. Here, |T| denotes the length of T.
• The 1-st through (\frac{|T|+1}{2} - 1)-th characters are all 1.
• The (\frac{|T|+1}{2})-th character is /.
• The (\frac{|T|+1}{2} + 1)-th through |T|-th characters are all 2.

For example, 11/22, 111/222, and / are 11/22 strings, but 1122, 1/22, 11/2222, 22/11, and //2/2/211 are not.

You are given a string S of length N consisting of 1, 2, and /, where S contains at least one /.
Find the maximum length of a (contiguous) substring of S that is an 11/22 string.

Constraints

• 1 \leq N \leq 2 \times 10^5
• S is a string of length N consisting of 1, 2, and /.
• S contains at least one /.

Sample Input 1

8
211/2212

Sample Output 1

5

The substring from the 2-nd to 6-th character of S is 11/22, which is an 11/22 string. Among all substrings of S that are 11/22 strings, this is the longest. Therefore, the answer is 5.

Sample Input 2

5
22/11

Sample Output 2

1

Sample Input 3

22
/1211/2///2111/2222/11

Sample Output 3

7

Problem Statement

For positive integers x and y, define f(x,y) as follows:

• Let z be the string obtained by interpreting x,y in decimal notation as strings and concatenating them in this order. Let f(x,y) be the value when z is interpreted as an integer in decimal notation.

For example, f(3,14)=314,\ f(100,3)=1003.

You are given positive integers C and D. Find the number of integers x that satisfy the following conditions:

• 1 \leq x \leq D
• f(C, C+x) is a perfect square.

You are given T test cases, find the answer for each of them.

Constraints

• 1 \leq T \leq 3 \times 10^5
• 1 \leq C \leq 2 \times 10^8
• 1 \leq D \leq 5 \times 10^9
• All input values are integers.

Sample Input 1

4
4 80
183 5000
18 10
824 5000000000

Sample Output 1

3
2
0
1421

For the first test case, there are three values of x that satisfy the conditions: x = 5, 37, 80.

• When x=5, f(C, C+5) = f(4,9) = 49 = 7^2
• When x=37, f(C, C+37) = f(4,41) = 441 = 21^2
• When x=80, f(C, C+80) = f(4,84) = 484 = 22^2

For the second test case, there are two values of x that satisfy the conditions: x = 1, 3133.

• When x=1, f(C, C+1) = f(183,184) = 183184 = 428^2
• When x=3133, f(C, C+3133) = f(183,3316) = 1833316 = 1354^2

For the third test case, there are zero values of x that satisfy the conditions.

For the fourth test case, there are 1421 values of x that satisfy the conditions.

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

You are given an undirected graph G with N vertices and M edges. G is simple (it has no self-loops and multiple edges) and connected.

For i = 1, 2, \ldots, M, the i-th edge is an undirected edge \lbrace u_i, v_i \rbrace connecting Vertices u_i and v_i.

Construct two spanning trees T_1 and T_2 of G that satisfy both of the two conditions below. (T_1 and T_2 do not necessarily have to be different spanning trees.)

• T_1 satisfies the following.

  If we regard T_1 as a rooted tree rooted at Vertex 1, for any edge \lbrace u, v \rbrace of G not contained in T_1, one of u and v is an ancestor of the other in T_1.

• T_2 satisfies the following.

  If we regard T_2 as a rooted tree rooted at Vertex 1, there is no edge \lbrace u, v \rbrace of G not contained in T_2 such that one of u and v is an ancestor of the other in T_2.

We can show that there always exists T_1 and T_2 that satisfy the conditions above.

Constraints

• 2 \leq N \leq 2 \times 10^5
• N-1 \leq M \leq \min\lbrace 2 \times 10^5, N(N-1)/2 \rbrace
• 1 \leq u_i, v_i \leq N
• All values in input are integers.
• The given graph is simple and connected.

Sample Input 1

6 8
5 1
4 3
1 4
3 5
1 2
2 6
1 6
4 2

Sample Output 1

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

In the Sample Output above, T_1 is a spanning tree of G containing 5 edges \lbrace 1, 4 \rbrace, \lbrace 4, 3 \rbrace, \lbrace 5, 3 \rbrace, \lbrace 4, 2 \rbrace, \lbrace 6, 2 \rbrace. This T_1 satisfies the condition in the Problem Statement. Indeed, for each edge of G not contained in T_1:

• for edge \lbrace 5, 1 \rbrace, Vertex 1 is an ancestor of 5;
• for edge \lbrace 1, 2 \rbrace, Vertex 1 is an ancestor of 2;
• for edge \lbrace 1, 6 \rbrace, Vertex 1 is an ancestor of 6.

T_2 is another spanning tree of G containing 5 edges \lbrace 1, 5 \rbrace, \lbrace 5, 3 \rbrace, \lbrace 1, 4 \rbrace, \lbrace 2, 1 \rbrace, \lbrace 1, 6 \rbrace. This T_2 satisfies the condition in the Problem Statement. Indeed, for each edge of G not contained in T_2:

• for edge \lbrace 4, 3 \rbrace, Vertex 4 is not an ancestor of Vertex 3, and vice versa;
• for edge \lbrace 2, 6 \rbrace, Vertex 2 is not an ancestor of Vertex 6, and vice versa;
• for edge \lbrace 4, 2 \rbrace, Vertex 4 is not an ancestor of Vertex 2, and vice versa.

Sample Input 2

4 3
3 1
1 2
1 4

Sample Output 2

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

Tree T, containing 3 edges \lbrace 1, 2\rbrace, \lbrace 1, 3 \rbrace, \lbrace 1, 4 \rbrace, is the only spanning tree of G. Since there are no edges of G that are not contained in T, obviously this T satisfies the conditions for both T_1 and T_2.