Problem Statement

You are given an integer K.

Print a string that is a concatenation of the first K uppercase English letters in ascending order, starting from A.

Constraints

• K is an integer between 1 and 26, inclusive.

Sample Input 1

3

Sample Output 1

ABC

The uppercase English letters in ascending order are A, B, C, ...

By concatenating the first three uppercase English letters, we get ABC.

Sample Input 2

1

Sample Output 2

A

Problem Statement

N participants, numbered 1 to N, will participate in a contest with M problems, numbered 1 to M.

For an integer i between 1 and N and an integer j between 1 and M, participant i can solve problem j if the j-th character of S_i is o, and cannot solve it if that character is x.

The participants must be in pairs. Print the number of ways to form a pair of participants who can collectively solve all the M problems.

More formally, print the number of pairs (x,y) of integers satisfying 1\leq x < y\leq N such that for any integer j between 1 and M, at least one of participant x and participant y can solve problem j.

Constraints

• N is an integer between 2 and 30, inclusive.
• M is an integer between 1 and 30, inclusive.
• S_i is a string of length M consisting of o and x.

Sample Input 1

5 5
ooooo
oooxx
xxooo
oxoxo
xxxxx

Sample Output 1

5

The following five pairs satisfy the condition: participants 1 and 2, participants 1 and 3, participants 1 and 4, participants 1 and 5, and participants 2 and 3.

On the other hand, the pair of participants 2 and 4, for instance, does not satisfy the condition because they cannot solve problem 4.

Sample Input 2

3 2
ox
xo
xx

Sample Output 2

1

Sample Input 3

2 4
xxxx
oxox

Sample Output 3

0

Problem Statement

You are given a string S of length N consisting of lowercase English letters, ,, and ". It is guaranteed that S contains an even number of ".

Let 2K be the number of " in S. For each i=1,2,\ldots,K, the characters from the (2i-1)-th " through the (2i)-th " are said to be enclosed.

Your task is to replace each , in S that is not an enclosed character with . and print the resulting string.

Constraints

• N is an integer between 1 and 2\times 10^5, inclusive.
• S is a string of length N consisting of lowercase English letters, ,, and ".
• S contains an even number of ".

Sample Input 1

8
"a,b"c,d

Sample Output 1

"a,b"c.d

In S, "a,b" are enclosed characters, and c,d are not.

The , in S that is not an enclosed character is the seventh character from the left in S, so replace that character with . to get the answer.

Sample Input 2

5
,,,,,

Sample Output 2

.....

Sample Input 3

20
a,"t,"c,"o,"d,"e,"r,

Sample Output 3

a."t,"c."o,"d."e,"r.

Problem Statement

You are given a simple undirected graph G with N vertices and M edges (a simple graph does not contain self-loops or multi-edges). For i = 1, 2, \ldots, M, the i-th edge connects vertex u_i and vertex v_i.

Print the number of pairs of integers (u, v) that satisfy 1 \leq u \lt v \leq N and both of the following conditions.

• The graph G does not have an edge connecting vertex u and vertex v.
• Adding an edge connecting vertex u and vertex v in the graph G results in a bipartite graph.

Constraints

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

Sample Input 1

5 4
4 2
3 1
5 2
3 2

Sample Output 1

2

We have two pairs of integers (u, v) that satisfy the conditions in the problem statement: (1, 4) and (1, 5). Thus, you should print 2.
The other pairs do not satisfy the conditions. For instance, for (1, 3), the graph G has an edge connecting vertex 1 and vertex 3; for (4, 5), adding an edge connecting vertex 4 and vertex 5 in the graph G does not result in a bipartite graph.

Sample Input 2

4 3
3 1
3 2
1 2

Sample Output 2

0

Note that the given graph may not be bipartite or connected.

Sample Input 3

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

Sample Output 3

9

Problem Statement

A box contains N balls, each with an integer between 1 and M-1 written on it. For i = 1, 2, \ldots, N, the integer written on the i-th ball is A_i.

While the box has two or more balls remaining, Takahashi will repeat the following.

• First, choose two balls arbitrarily.
• Then, get a score equal to the remainder when x^y + y^x is divided by M, where x and y are the integers written on the two balls.
• Finally, choose one of the two balls arbitrarily, eat it, and return the other to the box.

Print the maximum possible total score Takahashi will get.

Constraints

• 2 \leq N \leq 500
• 2 \leq M \leq 10^9
• 1 \leq A_i \leq M-1
• All values in the input are integers.

Sample Input 1

4 10
4 2 3 2

Sample Output 1

20

Consider the following scenario. Below, X \bmod Y denotes the remainder when a non-negative integer X is divided by a positive integer Y.

1. Take the first and third balls from the box to score (4^3 + 3^4) \bmod 10 = 5 points. Then, eat the first ball and return the third to the box. Now, the box has the second, third, and fourth balls.
2. Take the third and fourth balls from the box to score (3^2 + 2^3) \bmod 10 = 7 points. Then, eat the third ball and return the fourth to the box. Now, the box has the second and fourth balls.
3. Take the second and fourth balls from the box to score (2^2 + 2^2) \bmod 10 = 8 points. Then, eat the second ball and return the fourth to the box. Now, the box has just the fourth ball.

Here, Takahashi scores a total of 5 + 7 + 8 = 20 points, which is the maximum possible value.

Sample Input 2

20 100
29 31 68 20 83 66 23 84 69 96 41 61 83 37 52 71 18 55 40 8

Sample Output 2

1733

Problem Statement

This is an interactive task, where your and the judge's programs interact via Standard Input and Output.

You and the judge will follow the procedure below. The procedure consists of phases 1 and 2; phase 1 is immediately followed by phase 2.

(Phase 1)

• The judge gives you an integer N.
• You print an integer M between 1 and 50000, inclusive.
• You also print M pairs of integers (l_1, r_1), (l_2, r_2), \ldots, (l_M, r_M) such that 1 \leq l_i \leq r_i \leq N for every i = 1, 2, \ldots, M (the M pairs do not have to be distinct).

(Phase 2)

• The judge gives you an integer Q.
• You and the judge repeats the following Q times.
  • The judge gives you two integers L and R as a query.
  • You respond with two integers a and b between 1 and M, inclusive (possibly with a = b). Here, a and b must satisfy the condition below. Otherwise, your submission will be judged incorrect.
    • The union of the set \lbrace l_a, l_a+1, \ldots, r_a\rbrace and the set \lbrace l_b, l_b+1, \ldots, r_b\rbrace equals the set \lbrace L, L+1, \ldots, R\rbrace.

After the procedure above, terminate the program immediately to be judged correct.

Constraints

• 1 \leq N \leq 4000
• 1 \leq Q \leq 10^5
• 1 \leq L \leq R \leq N
• All values in the input are integers.

Input and Output

This is an interactive task, where your and the judge's programs interact via Standard Input and Output.

(Phase 1)

• First, N is given from the input.
• Next, an integer M between 1 and 50000, inclusive, should be printed.
• Then, (l_1, r_1), (l_2, r_2), \ldots, (l_M, r_M) should be printed, one at a time. Specifically, for each i = 1, 2, \ldots, M, the i-th output should be (l_i, r_i) in the following format:

l_i r_i

(Phase 2)

• First, Q is given from the input.
• In each query, integers L and R representing the query are given in the following format:

L R

• In response to each query, two integers a and b should be printed in the following format:

a b

Cautions

• At the end of each output, print a newline and flush Standard Output. Otherwise, you may get the TLE verdict.
• If your program prints a malformed output or quits prematurely, the verdict will be indeterminate. Particularly, note that in case of a runtime error, the verdict may be WA or TLE instead of RE.
• After phase 2, immediately terminate the program. Otherwise, the verdict will be indeterminate.
• L and R given in phase 2 will be decided according to (l_1, r_1), (l_2, r_2), \ldots, (l_M, r_M) you print in phase 1.

Sample Interaction

Below is a sample interaction with N = 4 and Q = 4.

Problem Statement

Below, a permutation of (1,2,\ldots,N) is simply called a permutation.

For two permutations A=(A_1,A_2,\ldots,A_N),B=(B_1,B_2,\ldots,B_N), let us define their similarity as the number of integers i between 1 and N-1 such that:

• (A_{i+1}-A_i)(B_{i+1}-B_i)>0.

Find the number, modulo a prime number P, of pairs of permutations (A,B) whose similarity is K.

Constraints

• 2\leq N \leq 100
• 0\leq K \leq N-1
• 10^8 \leq P \leq 10^9
• P is a prime number.
• All values in the input are integers.

Sample Input 1

3 1 282282277

Sample Output 1

16

For instance, below is a pair of permutations that satisfies the condition.

• A=(1,2,3)
• B=(1,3,2)

Here, we have (A_2 - A_1)(B_2 -B_1) > 0 and (A_3 - A_2)(B_3 -B_2) < 0, so the similarity of A and B is 1.

Sample Input 2

50 25 998244353

Sample Output 2

131276976

Print the number modulo P.

Problem Statement

You are given two sequences of integers of length N: A = (A_1, A_2, \ldots, A_N) and B = (B_1, B_2, \ldots, B_N).

Print the number of pairs of integers (l, r) that satisfy 1 \leq l \leq r \leq N and the following condition.

• \min\lbrace A_l, A_{l+1}, \ldots, A_r \rbrace + (B_l + B_{l+1} + \cdots + B_r) \leq S

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq S \leq 3 \times 10^{14}
• 0 \leq A_i \leq 10^{14}
• 0 \leq B_i \leq 10^9
• All values in the input are integers.

Sample Input 1

4 15
9 2 6 5
3 5 8 9

Sample Output 1

6

The following six pairs of integers (l, r) satisfy 1 \leq l \leq r \leq N and the condition in the problem statement: (1, 1), (1, 2), (2, 2), (2, 3), (3, 3), and (4, 4).

Sample Input 2

15 100
39 9 36 94 40 26 12 26 28 66 73 85 62 5 20
0 0 7 7 0 5 5 0 7 9 9 4 2 5 2

Sample Output 2

119