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.