Problem Statement

We have five cards with integers A, B, C, D, and E written on them, one on each card.

This set of five cards is called a Full house if and only if the following condition is satisfied:

• the set has three cards with a same number written on them, and two cards with another same number written on them.

Determine whether the set is a Full house.

Constraints

• 1 \leq A,B,C,D,E\leq 13
• Not all of A, B, C, D, and E are the same.
• All values in input are integers.

Sample Input 1

1 2 1 2 1

Sample Output 1

Yes

The set has three cards with 1 written on them and two cards with 2 written on them, so it is a Full house.

Sample Input 2

12 12 11 1 2

Sample Output 2

No

The condition is not satisfied.

Problem Statement

You are given an integer sequence A=(A_1,A_2,\dots,A_N) of length N and an integer X.
Determine whether X is contained in A.

Constraints

• All input values are integers.
• 1 \le N \le 100
• 1 \le A_i \le 100
• 1 \le X \le 100

Sample Input 1

5
3 1 4 1 5
4

Sample Output 1

Yes

We have A=(3,1,4,1,5) and X=4; X is contained in A.

Sample Input 2

4
100 100 100 100
100

Sample Output 2

Yes

X may be contained in A multiple times.

Sample Input 3

6
2 3 5 7 11 13
1

Sample Output 3

No

Problem Statement

You are given integer sequences, each of length N: A = (A_1, A_2, \dots, A_N) and B = (B_1, B_2, \dots, B_N).
All elements of A are different. All elements of B are different, too.

Print the following two values.

1. The number of integers contained in both A and B, appearing at the same position in the two sequences. In other words, the number of integers i such that A_i = B_i.
2. The number of integers contained in both A and B, appearing at different positions in the two sequences. In other words, the number of pairs of integers (i, j) such that A_i = B_j and i \neq j.

Constraints

• 1 \leq N \leq 1000
• 1 \leq A_i \leq 10^9
• 1 \leq B_i \leq 10^9
• A_1, A_2, \dots, A_N are all different.
• B_1, B_2, \dots, B_N are all different.
• All values in input are integers.

Sample Input 1

4
1 3 5 2
2 3 1 4

Sample Output 1

1
2

There is one integer contained in both A and B, appearing at the same position in the two sequences: A_2 = B_2 = 3.
There are two integers contained in both A and B, appearing at different positions in the two sequences: A_1 = B_3 = 1 and A_4 = B_1 = 2.

Sample Input 2

3
1 2 3
4 5 6

Sample Output 2

0
0

In both 1. and 2., no integer satisfies the condition.

Sample Input 3

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

Sample Output 3

3
2

Problem Statement

Takahashi is health-conscious and concerned about whether he is getting enough of M types of nutrients from his diet.

For the i-th nutrient, his goal is to take at least A_i units per day.

Today, he ate N foods, and from the i-th food, he took X_{i,j} units of nutrient j.

Determine whether he has met the goal for all M types of nutrients.

Constraints

• 1 \leq N \leq 100
• 1 \leq M \leq 100
• 0 \leq A_i, X_{i,j} \leq 10^7
• All input values are integers.

Sample Input 1

2 3
10 20 30
20 0 10
0 100 100

Sample Output 1

Yes

For nutrient 1, Takahashi took 20 units from the 1-st food and 0 units from the 2-nd food, totaling 20 units, thus meeting the goal of taking at least 10 units.
Similarly, he meets the goal for nutrients 2 and 3.

Sample Input 2

2 4
10 20 30 40
20 0 10 30
0 100 100 0

Sample Output 2

No

The goal is not met for nutrient 4.

Problem Statement

There are N buildings arranged in a line at equal intervals. The height of the i-th building from the front is H_i.

You want to decorate some of these buildings with illuminations so that both of the following conditions are satisfied:

• The chosen buildings all have the same height.
• The chosen buildings are arranged at equal intervals.

What is the maximum number of buildings you can choose? If you choose exactly one building, it is considered to satisfy the conditions.

Constraints

• 1 \leq N \leq 3000
• 1 \leq H_i \leq 3000
• All input values are integers.

Sample Input 1

8
5 7 5 7 7 5 7 7

Sample Output 1

3

Choosing the 2nd, 5th, and 8th buildings from the front satisfies the conditions.

Sample Input 2

10
100 200 300 400 500 600 700 800 900 1000

Sample Output 2

1

Choosing just one building is considered to satisfy the conditions.

Sample Input 3

32
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 5

Sample Output 3

3

Problem Statement

You are given strictly increasing sequences of length N and M: A=(A _ 1,A _ 2,\ldots,A _ N) and B=(B _ 1,B _ 2,\ldots,B _ M). Here, A _ i\neq B _ j for every i and j (1\leq i\leq N,1\leq j\leq M).

Let C=(C _ 1,C _ 2,\ldots,C _ {N+M}) be a strictly increasing sequence of length N+M that results from the following procedure.

• Let C be the concatenation of A and B. Formally, let C _ i=A _ i for i=1,2,\ldots,N, and C _ i=B _ {i-N} for i=N+1,N+2,\ldots,N+M.
• Sort C in ascending order.

For each of A _ 1,A _ 2,\ldots,A _ N, B _ 1,B _ 2,\ldots,B _ M, find its position in C. More formally, for each i=1,2,\ldots,N, find k such that C _ k=A _ i, and for each j=1,2,\ldots,M, find k such that C _ k=B _ j.

Constraints

• 1\leq N,M\leq 10^5
• 1\leq A _ 1\lt A _ 2\lt\cdots\lt A _ N\leq 10^9
• 1\leq B _ 1\lt B _ 2\lt\cdots\lt B _ M\leq 10^9
• A _ i\neq B _ j for every i and j (1\leq i\leq N,1\leq j\leq M).
• All values in the input are integers.

Sample Input 1

4 3
3 14 15 92
6 53 58

Sample Output 1

1 3 4 7
2 5 6

C will be (3,6,14,15,53,58,92). Here, the 1-st, 3-rd, 4-th, 7-th elements are from A=(3,14,15,92), and the 2-nd, 5-th, 6-th elements are from B=(6,53,58).

Sample Input 2

4 4
1 2 3 4
100 200 300 400

Sample Output 2

1 2 3 4
5 6 7 8

Sample Input 3

8 12
3 4 10 15 17 18 22 30
5 7 11 13 14 16 19 21 23 24 27 28

Sample Output 3

1 2 5 9 11 12 15 20
3 4 6 7 8 10 13 14 16 17 18 19

Problem Statement

Takahashi will receive N presents.

He has a parameter called mood, which is a non-negative integer, and his mood changes every time he receives a present. Each present has three parameters: value P, mood increase A, and mood decrease B, and his mood changes as follows based on these parameters:

• When the value P of the received present is greater than or equal to his mood, he is happy with the present, and his mood increases by A.
• When the value P of the received present is less than his mood, he is disappointed with the present, and his mood decreases by B. However, if his mood is originally less than B, it becomes 0.

The i-th (1\le i\le N) present he receives has value P _ i, mood increase A _ i, and mood decrease B _ i.

You are given Q questions, so answer all of them. In the i-th (1\le i\le Q) question, you are given a non-negative integer X _ i, so answer the following question:

Find Takahashi's mood after receiving all N presents when his mood is initially X _ i.

Constraints

• 1\le N\le10000
• 1\le P _ i\le500\ (1\le i\le N)
• 1\le A _ i\le500\ (1\le i\le N)
• 1\le B _ i\le500\ (1\le i\le N)
• 1\le Q\le5\times10 ^ 5
• 0\le X _ i\le10 ^ 9\ (1\le i\le Q)
• All input values are integers.

Sample Input 1

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

Sample Output 1

6
0
0
0
5
6
0
0
0
0
0

When Takahashi's initial mood is 10, his mood changes as follows:

• The value 3 of the first present is less than his mood 10, so his mood decreases by the mood decrease 4, and his mood becomes 6.
• The value 1 of the second present is less than his mood 6, and Takahashi's mood 6 is less than the mood decrease 9, so his mood becomes 0.
• The value 2 of the third present is not less than his mood 0, so his mood increases by the mood increase 6, and his mood becomes 6.
• The value 3 of the fourth present is less than his mood 6, and Takahashi's mood 6 is less than the mood decrease 8, so his mood becomes 0.

Therefore, his final mood is 0.

Sample Input 2

3
500 500 500
500 500 500
500 500 500
1
1000000000

Sample Output 2

999998500

Because Takahashi's mood is too high, his mood keeps decreasing even when he receives the best presents.

Sample Input 3

20
124 370 105
280 200 420
425 204 302
435 141 334
212 287 231
262 410 481
227 388 466
222 314 366
307 205 401
226 460 452
336 291 119
302 104 432
478 348 292
246 337 403
102 404 371
368 399 417
291 416 351
236 263 231
170 415 482
101 339 184
20
1162
1394
1695
2501
3008
3298
4053
4093
4330
5199
5302
5869
5875
6332
6567
7483
7562
7725
9723
9845

Sample Output 3

339
339
339
339
339
339
339
339
339
339
339
339
339
389
339
643
722
885
2883
3005

Problem Statement

You have an integer 1 and a die that shows integers between 1 and 6 (inclusive) with equal probability.
You repeat the following operation while your integer is strictly less than N:

• Cast a die. If it shows x, multiply your integer by x.

Find the probability, modulo 998244353, that your integer ends up being N.

Constraints

• 2 \leq N \leq 10^{18}
• N is an integer.

Sample Input 1

6

Sample Output 1

239578645

One of the possible procedures is as follows.

• Initially, your integer is 1.
• You cast a die, and it shows 2. Your integer becomes 1 \times 2 = 2.
• You cast a die, and it shows 4. Your integer becomes 2 \times 4 = 8.
• Now your integer is not less than 6, so you terminate the procedure.

Your integer ends up being 8, which is not equal to N = 6.

The probability that your integer ends up being 6 is \frac{7}{25}. Since 239578645 \times 25 \equiv 7 \pmod{998244353}, print 239578645.

Sample Input 2

7

Sample Output 2

0

No matter what the die shows, your integer never ends up being 7.

Sample Input 3

300

Sample Output 3

183676961

Sample Input 4

979552051200000000

Sample Output 4

812376310

Problem Statement

Snuke is planning on giving one gift each to Takahashi and Aoki.
There are N candidates for the gifts. Takahashi's impression of the i-th candidate is A_i, and Aoki's impression of it is B_i.

The two are very jealous. If Takahashi's impression of the gift Aoki gets is greater than Takahashi's impression of the gift Takahashi gets, Takahashi gets jealous of Aoki and starts fighting, and vice versa.

Among the N^2 possible ways of giving the gifts, how many do not lead to fighting?

Constraints

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

Sample Input 1

3
50 100 150
1 3 2

Sample Output 1

4

For example, if we give the 1-st candidate to Takahashi and the 2-nd candidate to Aoki, Takahashi's impression of the gift Aoki gets is 100, while Takahashi's impression of the gift Takahashi gets is 50, so Takahashi gets jealous of Aoki and starts fighting.

As another example, if we give the 3-rd candidate to Takahashi and the 2-nd candidate to Aoki, the two will not start fighting.

Note that it is allowed to give the same gift to the two.

Sample Input 2

3
123456789 123456 123
987 987654 987654321

Sample Output 2

6

Sample Input 3

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

Sample Output 3

37