Problem Statement

You are given a string S consisting of <, =, and >.
Determine whether S is a bidirectional arrow string.
A string S is a bidirectional arrow string if and only if there is a positive integer k such that S is a concatenation of one <, k =s, and one >, in this order, with a length of (k+2).

Constraints

• S is a string of length between 3 and 100, inclusive, consisting of <, =, and >.

Sample Input 1

<====>

Sample Output 1

Yes

<====> is a concatenation of one <, four =s, and one >, in this order, so it is a bidirectional arrow string.
Hence, print Yes.

Sample Input 2

==>

Sample Output 2

No

==> does not meet the condition for a bidirectional arrow string.
Hence, print No.

Sample Input 3

<>>

Sample Output 3

No

Problem Statement

Takahashi has N items and one bag.

The size of the i-th (1\le i\le N) item is A_i, and the size of the bag is M.

If and only if the total size of the items he is trying to put in the bag is at most M, he can put all those items in the bag simultaneously.

If he can put all N items in the bag simultaneously, print Yes; otherwise, print No.

Constraints

• 1\le N\le100
• 1\le M\le10000
• 1\le A_i\le100\ (1\le i\le N)
• All input values are integers.

Sample Input 1

5 15
3 1 4 1 5

Sample Output 1

Yes

The total size of the 5 items is 3+1+4+1+5=14. Since this is not greater than the bag size 15, Takahashi can put all items in the bag simultaneously. Thus, print Yes.

Sample Input 2

5 5
3 1 4 1 5

Sample Output 2

No

The total size of the 5 items is 14, which is greater than the bag size 5, so he cannot put all items in the bag simultaneously. Thus, print No.

Sample Input 3

1 10000
100

Sample Output 3

Yes

Problem Statement

Print the color of the cell at the R-th row from the top and C-th column from the left in the following grid with 15 vertical rows and 15 horizontal columns.

Constraints

• 1 \leq R, C \leq 15
• R and C are integers.

Sample Input 1

3 5

Sample Output 1

black

In the grid above, the cell at the 3-rd row from the top and 5-th column from the left is black. Thus, black should be printed.

Sample Input 2

4 5

Sample Output 2

white

In the grid above, the cell at the 4-th row from the top and 5-th column from the left is white. Thus, white should be printed.

Problem Statement

You are given a sequence of positive integers A=(A_1,A_2,\ldots,A_N) of length N.
Find the number of pairs of integers (l,r) satisfying 1\leq l\leq r\leq N that satisfy the following condition:

For every integer i satisfying l\leq i\leq r, A_i is not a divisor of A_l+A_{l+1}+\cdots+A_r.

Constraints

• 1 \leq N \leq 50
• 1 \leq A_i \leq 1000
• All input values are integers.

Sample Input 1

5
8 6 10 5 7

Sample Output 1

6

We have A=(8,6,10,5,7).

For example, (l,r)=(1,2) satisfies the condition because A_l+A_{l+1}+\cdots+A_r=A_1+A_2=14, and neither A_1=8 nor A_2=6 is a divisor of 14.
On the other hand, (l,r)=(1,3) does not satisfy the condition because A_l+A_{l+1}+\cdots+A_r=A_1+A_2+A_3=24, and A_1=8 is a divisor of 24.

The pairs that satisfy the condition are (l,r)=(1,2), (1,4), (2,3), (2,4), (3,5), (4,5), which is six pairs, so output 6.

Sample Input 2

3
1 1 1

Sample Output 2

0

Problem Statement

You are given a sequence of N positive integers A=(A_1,A_2,\dots,A_N).

Find the number of pairs of integers (l,r) satisfying 1\leq l\leq r\leq N such that the subsequence (A_l,A_{l+1},\dots,A_r) forms an arithmetic progression.

A sequence (x_1,x_2,\dots,x_{|x|}) is an arithmetic progression if and only if there exists a d such that x_{i+1}-x_i=d\ (1\leq i < |x|). In particular, a sequence of length 1 is always an arithmetic progression.

Constraints

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

Sample Input 1

4
3 6 9 3

Sample Output 1

8

There are eight pairs of integers (l,r) satisfying the condition: (1,1),(2,2),(3,3),(4,4),(1,2),(2,3),(3,4),(1,3).

Indeed, when (l,r)=(1,3), (A_l,\dots,A_r)=(3,6,9) is an arithmetic progression, so it satisfies the condition. However, when (l,r)=(2,4), (A_l,\dots,A_r)=(6,9,3) is not an arithmetic progression, so it does not satisfy the condition.

Sample Input 2

5
1 1 1 1 1

Sample Output 2

15

All pairs of integers (l,r)\ (1\leq l\leq r\leq 5) satisfy the condition.

Sample Input 3

8
87 42 64 86 72 58 44 30

Sample Output 3

22

Problem Statement

There are N items in a shop. For each i = 1, 2, \ldots, N, the price of the i-th item is A_i yen (the currency of Japan).

Takahashi has K coupons.
Each coupon can be used on one item. You can use any number of coupons, possibly zero, on the same item. Using k coupons on an item with a price of a yen allows you to buy it for \max\lbrace a - kX, 0\rbrace yen.

Print the minimum amount of money Takahashi needs to buy all the items.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq K, X \leq 10^9
• 1 \leq A_i \leq 10^9
• All values in input are integers.

Sample Input 1

5 4 7
8 3 10 5 13

Sample Output 1

12

By using 1 coupon on the 1-st item, 1 coupon on the 3-rd item, and 2 coupons on the 5-th item, Takahashi can:

• buy the 1-st item for \max\lbrace A_1-X, 0 \rbrace = 1 yen,
• buy the 2-nd item for \max\lbrace A_2, 0 \rbrace = 3 yen,
• buy the 3-rd item for \max\lbrace A_3-X, 0 \rbrace = 3 yen,
• buy the 4-th item for \max\lbrace A_4, 0 \rbrace = 5 yen,
• buy the 5-th item for \max\lbrace A_5-2X, 0 \rbrace = 0 yen,

for a total of 1 + 3 + 3 + 5 + 0 = 12 yen, which is the minimum possible.

Sample Input 2

5 100 7
8 3 10 5 13

Sample Output 2

0

Sample Input 3

20 815 60
2066 3193 2325 4030 3725 1669 1969 763 1653 159 5311 5341 4671 2374 4513 285 810 742 2981 202

Sample Output 3

112

Problem Statement

We have N distinct points on a two-dimensional plane, numbered 1,2,\ldots,N. Point i (1 \leq i \leq N) has the coordinates (x_i,y_i).

How many rectangles are there whose vertices are among the given points and whose edges are parallel to the x- or y-axis?

Constraints

• 4 \leq N \leq 2000
• 0 \leq x_i, y_i \leq 10^9
• (x_i,y_i) \neq (x_j,y_j) (i \neq j)
• All values in input are integers.

Sample Input 1

6
0 0
0 1
1 0
1 1
2 0
2 1

Sample Output 1

3

There are three such rectangles:

the rectangle whose vertices are Points 1, 2, 3, 4,

the rectangle whose vertices are Points 1, 2, 5, 6,

and the rectangle whose vertices are Points 3, 4, 5, 6.

Sample Input 2

4
0 1
1 2
2 3
3 4

Sample Output 2

0

Sample Input 3

7
0 1
1 0
2 0
2 1
2 2
3 0
3 2

Sample Output 3

1

Problem Statement

You have A apples, B oranges, C bananas, and D grapes.
How many ways are there to arrange these A+B+C+D fruits in a single row from left to right so that all of the following conditions hold? Find the count modulo 998244353.

• Every apple is placed to the left of every banana.
• Every apple is placed to the left of every grape.
• Every orange is placed to the left of every grape.

Here, the apples are indistinguishable; the same goes for the oranges, the bananas, and the grapes.

Constraints

• 1 \le A \le 10^6
• 1 \le B \le 10^6
• 1 \le C \le 10^6
• 1 \le D \le 10^6
• A, B, C, and D are integers.

Sample Input 1

1 1 1 1

Sample Output 1

5

There are five valid arrangements:

• apple, orange, banana, grape
• apple, orange, grape, banana
• apple, banana, orange, grape
• orange, apple, banana, grape
• orange, apple, grape, banana

Sample Input 2

1 2 4 8

Sample Output 2

2211

Sample Input 3

834150 21994 467364 994225

Sample Output 3

947921688

Problem Statement

There are N locations numbered 1 to N on a two-dimensional plane. Location i is at coordinates (X_i, Y_i).
You will start from location 1, visit every location exactly once, and return to location 1.
Moving from location i to location j takes \vert X_i - X_j \vert + \vert Y_i - Y_j \vert seconds.
Output a route that visits all locations and returns to location 1 within 10^{10} seconds of starting from location 1. It is guaranteed that at least one such route exists under the given constraints.

Constraints

• 1 \leq N \leq 6 \times 10^4
• 0 \leq X_i \leq 2 \times 10^7
• 0 \leq Y_i \leq 2 \times 10^7
• (X_i, Y_i) \neq (X_j, Y_j) if i \neq j
• All input values are integers.

Sample Input 1

3
0 6
3 5
2 4

Sample Output 1

1 3 2

\displaystyle \sum_{i=1}^N d(p_i, p_{(i \bmod N) + 1}) = 4 + 2 + 4 = 10, so the output satisfies the condition.

Sample Input 2

10
9706344 19786176
19341349 15565412
5711023 19068083
12521132 14054301
14767612 17088029
14961700 18526945
13801766 5740101
6581153 8643675
13176196 16586661
4086263 5172719

Sample Output 2

1 5 2 6 4 7 9 8 3 10