Problem Statement

Takahashi set task goals for N days.

He aimed to complete A_i tasks on day i (1 \leq i \leq N), and actually completed B_i tasks.

Find the number of days when he completed more tasks than his goal.

Constraints

• 1 \leq N \leq 100
• 1 \leq A_i, B_i \leq 100
• All input values are integers.

Sample Input 1

4
2 8
5 5
5 4
6 7

Sample Output 1

2

Takahashi completed more tasks than his goal on the 1st and 4th days.

Sample Input 2

5
1 1
1 1
1 1
1 1
1 1

Sample Output 2

0

Sample Input 3

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

Sample Output 3

3

Problem Statement

Takahashi wants to send a letter to Santa Claus. He has an envelope with an X-yen (Japanese currency) stamp stuck on it.
To be delivered to Santa Claus, the envelope must have stamps in a total value of at least Y yen.
Takahashi will put some more 10-yen stamps so that the envelope will have stamps worth at least Y yen in total.
At least how many more 10-yen stamps does Takahashi need to put on the envelope?

Constraints

• X and Y are integers.
• 1 \le X,Y \le 1000

Sample Input 1

80 94

Sample Output 1

2

• After adding zero 10-yen stamps to the 80-yen stamp, the total is 80 yen, which is less than the required amount of 94 yen.
• After adding one 10-yen stamp to the 80-yen stamp, the total is 90 yen, which is less than the required amount of 94 yen.
• After adding two 10-yen stamps to the 80-yen stamp, the total is 100 yen, which is not less than the required amount of 94 yen.

Sample Input 2

1000 63

Sample Output 2

0

The envelope may already have a stamp with enough value.

Sample Input 3

270 750

Sample Output 3

48

Problem Statement

You are given an integer N between -10^{18} and 10^{18} (inclusive).

Find an integer x between 0 and 998244353 - 1 (inclusive) that satisfies the following condition. It can be proved that such an integer is unique.

• N-x is a multiple of 998244353.

Constraints

• N is an integer between -10^{18} and 10^{18} (inclusive).

Sample Input 1

998244354

Sample Output 1

1

998244354-1 = 998244353 is a multiple of 998244353, so the condition is satisfied.

Sample Input 2

-9982443534

Sample Output 2

998244349

-9982443534-998244349= -10980687883 is a multiple of 998244353, so the condition is satisfied.

Problem Statement

You are given a string S of length at least 3 consisting of lowercase English letters.
S contains exactly two types of characters, and exactly one character is different from the others. Find that one character.

For example, if S is odd, report o.

Constraints

• S is a string of length at least 3 and at most 10 consisting of lowercase English letters.
• S contains exactly two types of characters, and exactly one character is different from the others.

Sample Input 1

odd

Sample Output 1

o

In odd, the character different from the others is o.

Sample Input 2

dad

Sample Output 2

a

In dad, the character different from the others is a.

Sample Input 3

wwwwwwwwwv

Sample Output 3

v

In wwwwwwwwwv, the character different from the others is v.

Problem Statement

Ringo-san is trying to paint a horse with stripes to make it a zebra.

There are N squares numbered 1 to N arranged in a line.
Initially, all squares are white, and the cost of painting square i black is C_i.

Consider performing the following procedure once to paint some squares black:

• Choose a positive integer x freely.
• Paint square i black for all integers i satisfying 1 \leq i \leq N such that the remainder when (i+x) is divided by 2W is less than W.

Find the minimum total cost to perform this procedure.

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 W \leq 2\times 10^5
• 1\leq C_i \leq 10^9
• The sum of N over the T test cases is at most 2\times 10^5.
• The sum of W over the T test cases is at most 2\times 10^5.
• All input values are integers.

Sample Input 1

4
8 2
1 10 10 1 1 10 10 1
8 3
1 10 10 1 1 10 10 1
8 4
1 10 10 1 1 10 10 1
4 100
100000 100000 100000 100000

Sample Output 1

4
12
22
0

In the first test case, if the procedure is executed with x=4, squares 1,4,5,8 are painted black, and the total cost is 4. The total cost cannot be less than 4, so this is the minimum.

Problem Statement

You are given an undirected graph with N vertices and M edges, where the vertices are numbered 1 through N and the edges are numbered 1 through M. Edge i connects vertices u_i and v_i.
To make the graph simple by removing edges, what is the minimum number of edges that must be removed?
Here, a graph is called simple if and only if it does not contain self-loops or multi-edges.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 5 \times 10^5
• 1 \leq u_i \leq N
• 1 \leq v_i \leq N
• All input values are integers.

Sample Input 1

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

Sample Output 1

2

By removing edges 3 and 5, the graph becomes simple. This is one of the ways to remove the minimum number of edges, so the answer is 2.

Sample Input 2

1 0

Sample Output 2

0

Sample Input 3

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

Sample Output 3

3

Problem Statement

You are given an integer sequence A=(A_1,A_2,\dots,A_N) of length N.
Find the number of triples of integers (i,j,k) that satisfy all of the following:

• 1 \le i,j,k \le N
• A_i : A_j : A_k = 7:5:3
• \min(i,j,k) = j or \max(i,j,k) = j.

Constraints

• All input values are integers.
• 1 \le N \le 3 \times 10^5
• 1 \le A_i \le 10^9

Sample Input 1

10
3 10 7 10 7 6 7 6 5 14

Sample Output 1

7

The seven triples of integers (i,j,k) that satisfy the conditions are:

• (3,9,1)
  • A_i : A_j : A_k = 7:5:3, and \max(i,j,k) = j.
• (5,9,1)
  • A_i : A_j : A_k = 7:5:3, and \max(i,j,k) = j.
• (7,9,1)
  • A_i : A_j : A_k = 7:5:3, and \max(i,j,k) = j.
• (10,2,6)
  • A_i : A_j : A_k = 14:10:6 = 7:5:3, and \min(i,j,k) = j.
• (10,2,8)
  • A_i : A_j : A_k = 14:10:6 = 7:5:3, and \min(i,j,k) = j.
• (10,4,6)
  • A_i : A_j : A_k = 14:10:6 = 7:5:3, and \min(i,j,k) = j.
• (10,4,8)
  • A_i : A_j : A_k = 14:10:6 = 7:5:3, and \min(i,j,k) = j.

Sample Input 2

6
210 210 210 210 210 210

Sample Output 2

0

Sample Input 3

21
49 30 50 21 35 15 21 70 35 9 50 70 21 49 30 50 70 15 9 21 30

Sample Output 3

34

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 boxes. The i-th box has a shape of a rectangular cuboid whose height, width, and depth are h_i,w_i, and d_i, respectively.

Determine if there are two boxes such that one's height, width, and depth are strictly greater than those of the other after rotating them if necessary.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq h_i,w_i,d_i \leq 10^9
• All input values are integers.

Sample Input 1

3
19 8 22
10 24 12
15 25 11

Sample Output 1

Yes

If you rotate the 2-nd box to swap its height and depth, the 3-rd box will have greater height, depth, and width.

Sample Input 2

3
19 8 22
10 25 12
15 24 11

Sample Output 2

No

Sample Input 3

2
1 1 2
1 2 2

Sample Output 3

No