Problem Statement

You are given two integers A and B, each between 0 and 9, inclusive.

Print any integer between 0 and 9, inclusive, that is not equal to A + B.

Constraints

• 0 \leq A \leq 9
• 0 \leq B \leq 9
• A + B \leq 9
• A and B are integers.

Sample Input 1

2 5

Sample Output 1

2

When A = 2, B = 5, we have A + B = 7. Thus, printing any of 0, 1, 2, 3, 4, 5, 6, 8, 9 is correct.

Sample Input 2

0 0

Sample Output 2

9

Sample Input 3

7 1

Sample Output 3

4

Problem Statement

You are given two positive integers A and B.

Output the square of A + B.

Constraints

• 1 \leq A,B \leq 2025
• All input values are integers.

Sample Input 1

20 25

Sample Output 1

2025

(20+25)^2=2025.

Sample Input 2

30 25

Sample Output 2

3025

Sample Input 3

45 11

Sample Output 3

3136

Sample Input 4

2025 1111

Sample Output 4

9834496

Problem Statement

Takahashi aggregated usage records from ticket gates. However, he accidentally erased some records of entering and exiting stations. He is trying to restore the erased records.

You are given a string S consisting of i and o. We want to insert zero or more characters at arbitrary positions in S so that the resulting string satisfies the following conditions:

• Its length is even, and every odd-numbered (1st, 3rd, ...) character is i while every even-numbered (2nd, 4th, ...) character is o.

Find the minimum number of characters that need to be inserted. It can be proved under the constraints of this problem that by inserting an appropriate finite number of characters, S can be made to satisfy the conditions.

Constraints

• S is a string of length between 1 and 100, consisting of i and o.

Sample Input 1

ioi

Sample Output 1

1

We can insert o after the 3rd character to form ioio to satisfy the conditions. The conditions cannot be satisfied by inserting zero or fewer characters.

Sample Input 2

iioo

Sample Output 2

2

We can insert o after the 1st character and i after the 3rd character to satisfy the conditions. The conditions cannot be satisfied by inserting one or fewer characters.

Sample Input 3

io

Sample Output 3

0

S already satisfies the conditions.

Problem Statement

You are given two positive integers N and M.

Let X = \displaystyle\sum_{i = 0}^{M} N^i. If X \leq 10^9, print the value of X. If X > 10^9, print inf.

Constraints

• 1 \leq N \leq 10^9
• 1 \leq M \leq 100
• All input values are integers.

Sample Input 1

7 3

Sample Output 1

400

X = 1 + 7 + 49 + 343 = 400. Since 400 \leq 10^9, print 400.

Sample Input 2

1000000 2

Sample Output 2

inf

X = 1000001000001 > 10^9, so print inf.

Sample Input 3

999999999 1

Sample Output 3

1000000000

Sample Input 4

998244353 99

Sample Output 4

inf

Problem Statement

Takahashi and Aoki will play the following game against each other.

Starting from Takahashi, the two alternatingly declare an integer between 1 and 2N+1 (inclusive) until the game ends. Any integer declared by either player cannot be declared by either player again. The player who is no longer able to declare an integer loses; the player who didn't lose wins.

In this game, Takahashi will always win. Your task is to actually play the game on behalf of Takahashi and win the game.

Constraints

• 1 \leq N \leq 1000
• N is an integer.

Input and Output

This task is an interactive task (in which your program and the judge program interact with each other via inputs and outputs).
Your program plays the game on behalf of Takahashi, and the judge program plays the game on behalf of Aoki.

First, your program is given a positive integer N from Standard Input. Then, the following procedures are repeated until the game ends.

1. Your program outputs an integer between 1 and 2N+1 (inclusive) to Standard Output, which defines the integer that Takahashi declares. (You cannot output an integer that is already declared by either player.)
2. The integer that Aoki declares is given by the judge program to your program from Standard Input. (No integer that is already declared by either player will be given.) If Aoki has no more integer to declare, 0 is given instead, which means that the game ended and Takahashi won.

Notes

• After each output, you must flush Standard Output. Otherwise, you may get TLE.
• After the game ended and Takahashi won, the program must be terminated immediately. Otherwise, the judge does not necessarily give AC.
• If your program outputs something that violates the rules of the game (such as an integer that has already been declared by either player), your answer is considered incorrect. In such case, the verdict is indeterminate. It does not necessarily give WA.

Sample Input and Output

Problem Statement

You are given simple undirected graphs G and H, each with N vertices: vertices 1, 2, \ldots, N. Graph G has M_G edges, and its i-th edge (1\leq i\leq M_G) connects vertices u_i and v_i. Graph H has M_H edges, and its i-th edge (1\leq i\leq M_H) connects vertices a_i and b_i.

You can perform the following operation on graph H any number of times, possibly zero.

• Choose a pair of integers (i,j) satisfying 1\leq i<j\leq N. Pay A_{i,j} yen, and if there is no edge between vertices i and j in H, add one; if there is, remove it.

Find the minimum total cost required to make G and H isomorphic.

Constraints

• 1\leq N\leq8
• 0\leq M _ G\leq\dfrac{N(N-1)}2
• 0\leq M _ H\leq\dfrac{N(N-1)}2
• 1\leq u _ i\lt v _ i\leq N\ (1\leq i\leq M _ G)
• (u _ i,v _ i)\neq(u _ j,v _ j)\ (1\leq i\lt j\leq M _ G)
• 1\leq a _ i\lt b _ i\leq N\ (1\leq i\leq M _ H)
• (a _ i,b _ i)\neq(a _ j,b _ j)\ (1\leq i\lt j\leq M _ H)
• 1\leq A _ {i,j}\leq 10 ^ 6\ (1\leq i\lt j\leq N)
• All input values are integers.

Sample Input 1

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

Sample Output 1

9

The given graphs are as follows:

For example, you can perform the following four operations on H to make it isomorphic to G at a cost of 9 yen.

• Choose (i,j)=(1,3). There is an edge between vertices 1 and 3 in H, so pay 1 yen to remove it.
• Choose (i,j)=(2,5). There is no edge between vertices 2 and 5 in H, so pay 2 yen to add it.
• Choose (i,j)=(1,5). There is an edge between vertices 1 and 5 in H, so pay 1 yen to remove it.
• Choose (i,j)=(3,5). There is no edge between vertices 3 and 5 in H, so pay 5 yen to add it.

After these operations, H becomes:

You cannot make G and H isomorphic at a cost less than 9 yen, so print 9.

Sample Input 2

5
3
1 2
2 3
3 4
4
1 2
2 3
3 4
4 5
9 1 1 1
1 1 1
1 1
9

Sample Output 2

3

For example, performing the operations (i,j)=(2,3),(2,4),(3,4) on H will make it isomorphic to G.

Sample Input 3

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

Sample Output 3

5

For example, performing the operation (i,j)=(4,5) once will make G and H isomorphic.

Sample Input 4

2
0
0
371

Sample Output 4

0

Note that G and H may have no edges.

Also, it is possible that no operations are needed.

Sample Input 5

8
13
1 8
5 7
4 6
1 5
7 8
1 6
1 2
5 8
2 6
5 6
6 7
3 7
4 8
15
3 5
1 7
4 6
3 8
7 8
1 2
5 6
1 6
1 5
1 4
2 8
2 6
2 4
4 7
1 3
7483 1694 5868 3296 9723 5299 4326
5195 4088 5871 1384 2491 6562
1149 6326 2996 9845 7557
4041 7720 1554 5060
8329 8541 3530
4652 3874
3748

Sample Output 5

21214

Problem Statement

In the country of AtCoder there are N zoos, numbered 1 to N. The admission fee for zoo i is C_i yen.

Mr. Suzuki likes M kinds of animals, animals 1,\dots,M.
Animal i can be seen at K_i zoos, namely zoos A_{i,1},\dots,A_{i,K_i}.

Find the minimum total admission fee required to see all M kinds of animals at least twice each.
If you visit the same zoo multiple times, the animals there are considered seen once per every visit.

Constraints

• 1 \le N \le 10
• 1 \le M \le 100
• 0 \le C_i \le 10^9
• 1 \le K_i \le N
• 1 \le A_{i,j} \le N
• j \neq j' \Longrightarrow A_{i,j} \neq A_{i,j'}
• All input values are integers.

Sample Input 1

4 3
1000 300 700 200
3 1 3 4
3 1 2 4
2 1 3

Sample Output 1

1800

For example, the following schedule achieves seeing animals 1,2,3 at least twice each for a total of 1800 yen:

• Go to zoo 3. Pay 700 yen and see animals 1 and 3.
• Go to zoo 3. Pay 700 yen and see animals 1 and 3.
• Go to zoo 4. Pay 200 yen and see animals 1 and 2.
• Go to zoo 4. Pay 200 yen and see animals 1 and 2.

Sample Input 2

7 6
500 500 500 500 500 500 1000
3 1 2 7
3 2 3 7
3 3 4 7
3 4 5 7
3 5 6 7
3 6 1 7

Sample Output 2

2000

By visiting zoo 7 twice, you can see animals 1,2,3,4,5,6 twice each for a total of 2000 yen.

Problem Statement

Takahashi has N pieces of chocolate. The i-th piece has a rectangular shape with a width of A_i centimeters and a length of B_i centimeters.
He also has M boxes. The i-th box has a rectangular shape with a width of C_i centimeters and a length of D_i centimeters.

Determine whether it is possible to put the N pieces of chocolate in the boxes under the conditions below.

• A box can contain at most one piece of chocolate.
• A_i \leq C_j and B_i \leq D_j must hold when putting the i-th piece of chocolate in the j-th box (they cannot be rotated).

Constraints

• 1 \leq N \leq M \leq 2\times 10^5
• 1 \leq A_i,B_i,C_i,D_i \leq 10^9
• All values in input are integers.

Sample Input 1

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

Sample Output 1

Yes

We can put the first piece of chocolate in the third box and the second piece in the first box.

Sample Input 2

2 2
1 1
2 2
100 1
100 1

Sample Output 2

No

A box can contain at most one piece of chocolate.

Sample Input 3

1 1
10
100
100
10

Sample Output 3

No

Sample Input 4

1 1
10
100
10
100

Sample Output 4

Yes

Problem Statement

You are given an integer sequence A of length N.

For each t = 1, 2, \dots, N, determine whether A_t is included in a longest increasing subsequence of A.

Here, A_t is included in a longest increasing subsequence of A if and only if the following holds:

• Let L be the length of a longest increasing subsequence of A. There exists a strictly increasing integer sequence i = (i_1, i_2, \dots, i_L) \ (i_1 < i_2 < \dots < i_L), where each element is between 1 and N, inclusive, that satisfies all of the following conditions:

  • A_{i_1} < A_{i_2} < \dots < A_{i_L}.
  • i_k = t for some k \ (1 \leq k \leq L).

You are given T test cases; solve each of them.

Constraints

• 1 \leq T \leq 2 \times 10^5
• 1 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq 10^9
• The sum of N across all test cases is at most 2 \times 10^5.

Sample Input 1

1
5
2 1 4 5 3

Sample Output 1

4
1 2 3 4

One of the longest increasing subsequences is (2, 4, 5), with a length of 3. Another longest increasing subsequence is (1, 4, 5). However, no longest increasing subsequence includes A_5.

Therefore, print 1, 2, 3, 4.

Sample Input 2

2
6
2 5 3 4 3 4
5
10000 1000 100 1 10

Sample Output 2

5
1 3 4 5 6
2
4 5