Problem Statement

Takahashi and Aoki will play a game against each other.
Initially, Takahashi and Aoki have A and B candies, respectively.
They will alternately do the operation below. Takahashi goes first if C=0, and Aoki goes first if C=1.

• Eat one of the candies he has.

The person who first becomes unable to do the operation loses. Which person will win?

Constraints

• All values in input are integers.
• 0 ≤ A, B ≤ 100
• C \in \{0, 1\}

Sample Input 1

2 1 0

Sample Output 1

Takahashi

Initially, Takahashi and Aoki have 2 and 1 candy(ies), respectively. The game will proceed as follows:

• Takahashi eats his candy.
• Aoki eats his candy.
• Takahashi eats his candy.
• Aoki has no more candies, so Takahashi wins.

Sample Input 2

2 2 0

Sample Output 2

Aoki

Sample Input 3

2 2 1

Sample Output 3

Takahashi

Problem Statement

Takahashi, the magician, is fighting with a monster.
He can use N spells.
The i-th spell takes X_i seconds to cast and has a power Y_i.
However, the monster is strong enough to avoid taking damage from spells taking S or more seconds to cast and spells with powers D or less.
Also, there is nothing other than spells that can do damage to the monster.
Can Takahashi do damage to the monster?

Constraints

• All values in input are integers.
• 1 ≤ N ≤ 100
• 1 ≤ X_i ≤ 10^9
• 1 ≤ Y_i ≤ 10^9
• 1 ≤ S ≤ 10^9
• 1 ≤ D ≤ 10^9

Sample Input 1

4 9 9
5 5
15 5
5 15
15 15

Sample Output 1

Yes

The second and fourth spells take too much time to do damage.
Also, the first and second spells do not have enough powers to do damage.
Thus, only the third spell can do damage.

Sample Input 2

3 691 273
691 997
593 273
691 273

Sample Output 2

No

Sample Input 3

7 100 100
10 11
12 67
192 79
154 197
142 158
20 25
17 108

Sample Output 3

Yes

Only the seventh spell can do damage.

Problem Statement

We have N dishes numbered 1, 2, \dots, N and M conditions numbered 1, 2, \dots, M.
Condition i is satisfied when both Dish A_i and Dish B_i have (one or more) balls on them.
There are K people numbered 1, 2, \dots, K. Person i will put a ball on Dish C_i or Dish D_i.
At most how many conditions will be satisfied?

Constraints

• All values in input are integers.
• 2 ≤ N ≤ 100
• 1 ≤ M ≤ 100
• 1 ≤ A_i < B_i ≤ N
• 1 ≤ K ≤ 16
• 1 ≤ C_i < D_i ≤ N

Sample Input 1

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

Sample Output 1

2

For example, if People 1, 2, 3 put their balls on Dishes 1, 3, 2, respectively, Conditions 1 and 2 will be satisfied.

Sample Input 2

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

Sample Output 2

4

For example, if People 1, 2, 3, 4 put their balls on Dishes 3, 1, 2, 4, respectively, all conditions will be satisfied.

Sample Input 3

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

Sample Output 3

9

Problem Statement

How many arithmetic progressions consisting of integers with a common difference of 1 have a sum of N?

Constraints

• 1 ≤ N ≤ 10^{12}
• N is an integer.

Sample Input 1

12

Sample Output 1

4

We have four such progressions:

• [12]
• [3, 4, 5]
• [-2, -1, 0, 1, 2, 3, 4, 5]
• [-11, -10, -9, \dots, 10, 11, 12]

Sample Input 2

1

Sample Output 2

2

We have two such progressions:

• [1]
• [0, 1]

Sample Input 3

963761198400

Sample Output 3

1920

Problem Statement

There are N kinds of magical gems, numbered 1, 2, \ldots, N, distributed in the AtCoder Kingdom.
Takahashi is trying to make an ornament by arranging gems in a row.
For some pairs of gems, we can put the two gems next to each other; for other pairs, we cannot. We have M pairs for which the two gems can be adjacent: (Gem A_1, Gem B_1), (Gem A_2, Gem B_2), \ldots, (Gem A_M, Gem B_M). For the other pairs, the two gems cannot be adjacent. (Order does not matter in these pairs.)
Determine whether it is possible to form a sequence of gems that has one or more gems of each of the kinds C_1, C_2, \dots, C_K. If the answer is yes, find the minimum number of stones needed to form such a sequence.

Constraints

• All values in input are integers.
• 1 ≤ N ≤ 10^5
• 0 ≤ M ≤ 10^5
• 1 ≤ A_i < B_i ≤ N
• If i ≠ j, (A_i, B_i) ≠ (A_j, B_j).
• 1 ≤ K ≤ 17
• 1 ≤ C_1 < C_2 < \dots < C_K ≤ N

Sample Input 1

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

Sample Output 1

5

For example, by arranging the gems in the order [1, 4, 2, 4, 3], we can form a sequence of length 5 with Gems 1, 2, 3.

Sample Input 2

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

Sample Output 2

-1

Sample Input 3

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

Sample Output 3

11

For example, by arranging the gems in the order [1, 6, 7, 5, 8, 3, 9, 3, 8, 10, 2], we can form a sequence of length 11 with Gems 1, 2, 7, 9.

Problem Statement

Given is a sequence A = [a_0, a_1, a_2, \dots, a_{N-1}] that is a permutation of 0, 1, 2, \dots, N - 1.
For each k = 0, 1, 2, \dots, N - 1, find the inversion number of the sequence B = [b_0, b_1, b_2, \dots, b_{N-1}] defined as b_i = a_{i+k \bmod N}.

Constraints

• All values in input are integers.
• 2 ≤ N ≤ 3 \times 10^5
• a_0, a_1, a_2, \dots, a_{N-1} is a permutation of 0, 1, 2, \dots, N - 1.

Sample Input 1

4
0 1 2 3

Sample Output 1

0
3
4
3

We have A = [0, 1, 2, 3].

For k = 0, the inversion number of B = [0, 1, 2, 3] is 0.
For k = 1, the inversion number of B = [1, 2, 3, 0] is 3.
For k = 2, the inversion number of B = [2, 3, 0, 1] is 4.
For k = 3, the inversion number of B = [3, 0, 1, 2] is 3.

Sample Input 2

10
0 3 1 5 4 2 9 6 8 7

Sample Output 2

9
18
21
28
27
28
33
24
21
14