Problem Statement

There was a contest with N problems. The i-th (1\leq i\leq N) problem was worth A_i points.

Snuke took part in this contest and solved M problems: the B_1-th, B_2-th, \ldots, and B_M-th ones. Find his total score.

Here, the total score is defined as the sum of the points for the problems he solved.

Constraints

• 1\leq M \leq N \leq 100
• 1\leq A_i \leq 100
• 1\leq B_1 < B_2 < \ldots < B_M \leq N
• All values in the input are integers.

Sample Input 1

3 2
10 20 30
1 3

Sample Output 1

40

Snuke solved the 1-st and 3-rd problems, which are worth 10 and 30 points, respectively. Thus, the total score is 10+30=40 points.

Sample Input 2

4 1
1 1 1 100
4

Sample Output 2

100

Sample Input 3

8 4
22 75 26 45 72 81 47 29
4 6 7 8

Sample Output 3

202

Problem Statement

A fruit store sells apples.
You may perform the following operations as many times as you want in any order:

• Buy one apple for X yen (the currency in Japan).
• Buy three apples for Y yen.

How much yen do you need to pay to obtain exactly N apples?

Constraints

• 1 \leq X \leq Y \leq 100
• 1 \leq N \leq 100
• All values in input are integers.

Sample Input 1

10 25 10

Sample Output 1

85

Buy three apples for 25 yen three times and one apple for 10 yen, and you will obtain exactly 10 apples for a total of 85 yen.
You cannot obtain exactly 10 apples for a lower cost, so the answer is 85 yen.

Sample Input 2

10 40 10

Sample Output 2

100

It is optimal to buy an apple for 10 yen 10 times.

Sample Input 3

100 100 2

Sample Output 3

200

The only way to obtain exactly 2 apples is to buy an apple for 100 yen twice.

Sample Input 4

100 100 100

Sample Output 4

3400

Problem Statement

There is a grid with H rows from top to bottom and W columns from left to right. Let (i, j) denote the square at the i-th row from the top and j-th column from the left.
The squares are described by characters C_{i,j}. If C_{i,j} is ., (i, j) is empty; if it is #, (i, j) contains a box.

For integers j satisfying 1 \leq j \leq W, let the integer X_j defined as follows.

• X_j is the number of boxes in the j-th column. In other words, X_j is the number of integers i such that C_{i,j} is #.

Find all of X_1, X_2, \dots, X_W.

Constraints

• 1 \leq H \leq 1000
• 1 \leq W \leq 1000
• H and W are integers.
• C_{i, j} is . or #.

Sample Input 1

3 4
#..#
.#.#
.#.#

Sample Output 1

1 2 0 3

In the 1-st column, one square, (1, 1), contains a box. Thus, X_1 = 1.
In the 2-nd column, two squares, (2, 2) and (3, 2), contain a box. Thus, X_2 = 2.
In the 3-rd column, no squares contain a box. Thus, X_3 = 0.
In the 4-th column, three squares, (1, 4), (2, 4), and (3, 4), contain a box. Thus, X_4 = 3.
Therefore, the answer is (X_1, X_2, X_3, X_4) = (1, 2, 0, 3).

Sample Input 2

3 7
.......
.......
.......

Sample Output 2

0 0 0 0 0 0 0

There may be no square that contains a box.

Sample Input 3

8 3
.#.
###
.#.
.#.
.##
..#
##.
.##

Sample Output 3

2 7 4

Sample Input 4

5 47
.#..#..#####..#...#..#####..#...#...###...#####
.#.#...#.......#.#...#......##..#..#...#..#....
.##....#####....#....#####..#.#.#..#......#####
.#.#...#........#....#......#..##..#...#..#....
.#..#..#####....#....#####..#...#...###...#####

Sample Output 4

0 5 1 2 2 0 0 5 3 3 3 3 0 0 1 1 3 1 1 0 0 5 3 3 3 3 0 0 5 1 1 1 5 0 0 3 2 2 2 2 0 0 5 3 3 3 3

Problem Statement

N people, person 1, person 2, \ldots, person N, are playing roulette. The outcome of a spin is one of the 37 integers from 0 to 36. For each i = 1, 2, \ldots, N, person i has bet on C_i of the 37 possible outcomes: A_{i, 1}, A_{i, 2}, \ldots, A_{i, C_i}.

The wheel has been spun, and the outcome is X. Print the numbers of all people who have bet on X with the fewest bets, in ascending order.

More formally, print all integers i between 1 and N, inclusive, that satisfy both of the following conditions, in ascending order:

• Person i has bet on X.
• For each j = 1, 2, \ldots, N, if person j has bet on X, then C_i \leq C_j.

Note that there may be no number to print (see Sample Input 2).

Constraints

• 1 \leq N \leq 100
• 1 \leq C_i \leq 37
• 0 \leq A_{i, j} \leq 36
• A_{i, 1}, A_{i, 2}, \ldots, A_{i, C_i} are all different for each i = 1, 2, \ldots, N.
• 0 \leq X \leq 36
• All input values are integers.

Sample Input 1

4
3
7 19 20
4
4 19 24 0
2
26 10
3
19 31 24
19

Sample Output 1

2
1 4

The wheel has been spun, and the outcome is 19. The people who has bet on 19 are person 1, person 2, and person 4, and the number of their bets are 3, 4, and 3, respectively. Therefore, among the people who has bet on 19, the ones with the fewest bets are person 1 and person 4.

Sample Input 2

3
1
1
1
2
1
3
0

Sample Output 2

0

The wheel has been spun and the outcome is 0, but no one has bet on 0, so there is no number to print.

Problem Statement

There are M sets, called S_1, S_2, \dots, S_M, consisting of integers between 1 and N.
S_i consists of C_i integers a_{i, 1}, a_{i, 2}, \dots, a_{i, C_i}.

There are (2^M-1) ways to choose one or more sets from the M sets.
How many of them satisfy the following condition?

• For all integers x such that 1 \leq x \leq N, there is at least one chosen set containing x.

Constraints

• 1 \leq N \leq 10
• 1 \leq M \leq 10
• 1 \leq C_i \leq N
• 1 \leq a_{i,1} \lt a_{i,2} \lt \dots \lt a_{i,C_i} \leq N
• All values in the input are integers.

Sample Input 1

3 3
2
1 2
2
1 3
1
2

Sample Output 1

3

The sets given in the input are S_1 = \lbrace 1, 2 \rbrace, S_2 = \lbrace 1, 3 \rbrace, S_3 = \lbrace 2 \rbrace.
The following three ways satisfy the conditions in the Problem Statement:

• choosing S_1, S_2;
• choosing S_1, S_2, S_3;
• choosing S_2, S_3.

Sample Input 2

4 2
2
1 2
2
1 3

Sample Output 2

0

There may be no way to choose sets that satisfies the conditions in the Problem Statement.

Sample Input 3

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

Sample Output 3

18

Problem Statement

A region has N towns numbered 1 to N, and M roads numbered 1 to M.

The i-th road connects town A_i and town B_i bidirectionally with length C_i.

Find the maximum possible total length of the roads you traverse when starting from a town of your choice and getting to another town without passing through the same town more than once.

Constraints

• 2 \leq N \leq 10
• 1 \leq M \leq \frac{N(N-1)}{2}
• 1 \leq A_i < B_i \leq N
• The pairs (A_i,B_i) are distinct.
• 1\leq C_i \leq 10^8
• All input values are integers.

Sample Input 1

4 4
1 2 1
2 3 10
1 3 100
1 4 1000

Sample Output 1

1110

If you travel as 4\to 1\to 3\to 2, the total length of the roads you traverse is 1110.

Sample Input 2

10 1
5 9 1

Sample Output 2

1

There may be a town that is not connected to a road.

Sample Input 3

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

Sample Output 3

20

Problem Statement

There is a sequence A = (A_0, A_1, \dots, A_{N - 1}) with N = 2^{20} terms. Initially, every term is -1.

Process Q queries in order. The i-th query (1 \leq i \leq Q) is described by an integer t_i such that t_i = 1 or t_i = 2, and another integer x_i, as follows.

• If t_i = 1, do the following in order.
  1. Define an integer h as h = x_i.
  2. While A_{h \bmod N} \neq -1, keep adding 1 to h. We can prove that this process ends after finite iterations under the Constraints of this problem.
  3. Replace the value of A_{h \bmod N} with x_i.
• If t_i = 2, print the value of A_{x_i \bmod N} at that time.

Here, for integers a and b, a \bmod b denotes the remainder when a is divided by b.

Constraints

• 1 \leq Q \leq 2 \times 10^5
• t_i \in \{ 1, 2 \} \, (1 \leq i \leq Q)
• 0 \leq x_i \leq 10^{18} \, (1 \leq i \leq Q)
• There is at least one i (1 \leq i \leq Q) such that t_i = 2.
• All values in input are integers.

Sample Input 1

4
1 1048577
1 1
2 2097153
2 3

Sample Output 1

1048577
-1

We have x_1 \bmod N = 1, so the first query sets A_1 = 1048577.

In the second query, initially we have h = x_2, for which A_{h \bmod N} = A_{1} \neq -1, so we add 1 to h. Now we have A_{h \bmod N} = A_{2} = -1, so this query sets A_2 = 1.

In the third query, we print A_{x_3 \bmod N} = A_{1} = 1048577.

In the fourth query, we print A_{x_4 \bmod N} = A_{3} = -1.

Note that, in this problem, N = 2^{20} = 1048576 is a constant and not given in input.

Problem Statement

Takahashi and Aoki are playing a game using N cards. The front side of the i-th card has A_i written on it, and the back side has B_i written on it. Initially, the N cards are laid out on the table. With Takahashi going first, the two players take turns performing the following operation:

• Choose a pair of cards from the table such that either the numbers on their front sides are the same or the numbers on their back sides are the same, and remove these two cards from the table. If no such pair of cards exists, the player cannot perform the operation.

The player who is first to be unable to perform the operation loses, and the other player wins. Determine who wins if both players play optimally.

Constraints

• 1 \leq N \leq 18
• 1 \leq A_i, B_i \leq 10^9
• All input values are integers.

Sample Input 1

5
1 9
2 5
4 9
1 4
2 5

Sample Output 1

Aoki

If Takahashi first removes

• the first and third cards: Aoki can win by removing the second and fifth cards.

• the first and fourth cards: Aoki can win by removing the second and fifth cards.

• the second and fifth cards: Aoki can win by removing the first and third cards.

These are the only three pairs of cards Takahashi can remove in his first move, and Aoki can win in all cases. Therefore, the answer is Aoki.

Sample Input 2

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

Sample Output 2

Takahashi

Problem Statement

There are N towns numbered 1,\ldots,N and M roads numbered 1,\ldots,M.

Road i connects towns A_i and B_i. When you use a road, your score changes as follows:

• when you move from town A_i to town B_i using road i, your score increases by C_i; when you move from town B_i to town A_i using road i, your score decreases by C_i.

Your score may become negative.

Answer the following Q questions.

• If you start traveling from town X_i with initial score 0, find the maximum possible score when you are at town Y_i.
  Here, if you cannot get from town X_i to town Y_i, print nan instead; if you can have as large a score as you want when you are at town Y_i, print inf instead.

Constraints

• 2\leq N \leq 10^5
• 0\leq M \leq 10^5
• 1\leq Q \leq 10^5
• 1\leq A_i,B_i,X_i,Y_i \leq N
• 0\leq C_i \leq 10^9
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

-2
inf
nan

For the first question, if you use road 5 to move from town 5 to town 3, you can have a score -2 when you are at town 3.
Since you cannot make the score larger, the answer is -2.

For the second question, you can have as large a score as you want when you are at town 2 if you travel as follows: repeatedly "use road 2 to move from town 1 to town 2 and then use road 1 to move from town 2 to town 1" as many times as you want, and finally use road 2 to move from town 1 to town 2.

For the third question, you cannot get from town 3 to town 1.

Sample Input 2

2 1 1
1 1 1
1 1

Sample Output 2

inf

The endpoints of a road may be the same, and so may the endpoints given in a question.

Sample Input 3

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

Sample Output 3

inf
nan
nan
inf
-9