Problem Statement

For a positive integer L, a level-L dango string is a string that satisfies the following conditions.

• It is a string of length L+1 consisting of o and -.
• Exactly one of the first character and the last character is -, and the other L characters are o.

For instance, ooo- is a level-3 dango string, but none of -ooo-, oo, and o-oo- is a dango string (more precisely, none of them is a level-L dango string for any positive integer L).

You are given a string S of length N consisting of the two characters o and -. Find the greatest positive integer X that satisfies the following condition.

• There is a contiguous substring of S that is a level-X dango string.

If there is no such integer, print -1.

Constraints

• 1\leq N\leq 2\times10^5
• S is a string of length N consisting of o and -.

Sample Input 1

10
o-oooo---o

Sample Output 1

4

For instance, the substring oooo- corresponding to the 3-rd through 7-th characters of S is a level-4 dango string. No substring of S is a level-5 dango string or above, so you should print 4.

Sample Input 2

1
-

Sample Output 2

-1

Only the empty string and - are the substrings of S. They are not dango strings, so you should print -1.

Sample Input 3

30
-o-o-oooo-oo-o-ooooooo--oooo-o

Sample Output 3

7

Problem Statement

Takahashi is on a two-dimensional plane. Starting from the origin, he made N moves.

The N moves are represented by a string of length N as described below:

• Takahashi's coordinates after the i-th move are:

  • (x+1,y) if the i-th character of S is R;
  • (x-1,y) if the i-th character of S is L;
  • (x,y+1) if the i-th character of S is U; and
  • (x,y-1) if the i-th character of S is D,

  where (x,y) is his coordinates before the move.

Determine if Takahashi visited the same coordinates multiple times in the course of the N moves (including the starting and ending points).

Constraints

• 1 \leq N \leq 2\times 10^5
• N is an integer.
• S is a string of length N consisting of R, L, U, and D.

Sample Input 1

5
RLURU

Sample Output 1

Yes

Takahashi's coordinates change as follows: (0,0)\to (1,0)\to (0,0)\to (0,1)\to (1,1)\to (1,2).

Sample Input 2

20
URDDLLUUURRRDDDDLLLL

Sample Output 2

No

Problem Statement

The Republic of AtCoder lies on a Cartesian coordinate plane.
It has N towns, numbered 1,2,\dots,N. Town i is at (x_i, y_i), and no two different towns are at the same coordinates.

There are teleportation spells in the nation. A spell is identified by a pair of integers (a,b), and casting a spell (a, b) at coordinates (x, y) teleports you to (x+a, y+b).

Snuke is a great magician who can learn the spell (a, b) for any pair of integers (a, b) of his choice. The number of spells he can learn is also unlimited.
To be able to travel between the towns using spells, he has decided to learn some number of spells so that it is possible to do the following for every pair of different towns (i, j).

• Choose just one spell among the spells learned. Then, repeatedly use just the chosen spell to get from Town i to Town j.

At least how many spells does Snuke need to learn to achieve the objective above?

Constraints

• 2 \leq N \leq 500
• 0 \leq x_i \leq 10^9 (1 \leq i \leq N)
• 0 \leq y_i \leq 10^9 (1 \leq i \leq N)
• (x_i, y_i) \neq (x_j, y_j) if i \neq j.

Sample Input 1

3
1 2
3 6
7 4

Sample Output 1

6

The figure below illustrates the positions of the towns (along with the coordinates of the four corners).

If Snuke learns the six spells below, he can get from Town i to Town j by using one of the spells once for every pair (i,j) (i \neq j), achieving his objective.

• (2, 4)
• (-2, -4)
• (4, -2)
• (-4, 2)
• (-6, -2)
• (6, 2)

Another option is to learn the six spells below. In this case, he can get from Town i to Town j by using one of the spells twice for every pair (i,j) (i \neq j), achieving his objective.

• (1, 2)
• (-1, -2)
• (2, -1)
• (-2, 1)
• (-3, -1)
• (3, 1)

There is no combination of spells that consists of less than six spells and achieve the objective, so we should print 6.

Sample Input 2

3
1 2
2 2
4 2

Sample Output 2

2

The optimal choice is to learn the two spells below:

• (1, 0)
• (-1, 0)

Sample Input 3

4
0 0
0 1000000000
1000000000 0
1000000000 1000000000

Sample Output 3

8

Problem Statement

Takahashi has a playlist with N songs. Song i (1 \leq i \leq N) lasts T_i seconds.
Takahashi has started random play of the playlist at time 0.

Random play repeats the following: choose one song from the N songs with equal probability and play that song to the end. Here, songs are played continuously: once a song ends, the next chosen song starts immediately. The same song can be chosen consecutively.

Find the probability that song 1 is being played (X + 0.5) seconds after time 0, modulo 998244353.

Constraints

• 2 \leq N\leq 10^3
• 0 \leq X\leq 10^4
• 1 \leq T_i\leq 10^4
• All input values are integers.

Sample Input 1

3 6
3 5 6

Sample Output 1

369720131

Song 1 will be playing 6.5 seconds after time 0 if songs are played in one of the following orders.

• Song 1 \to Song 1 \to Song 1
• Song 2 \to Song 1
• Song 3 \to Song 1

The probability that one of these occurs is \frac{7}{27}.
We have 369720131\times 27\equiv 7 \pmod{998244353}, so you should print 369720131.

Sample Input 2

5 0
1 2 1 2 1

Sample Output 2

598946612

0.5 seconds after time 0, the first song to be played is still playing, so the sought probability is \frac{1}{5}.
Note that different songs may have the same length.

Sample Input 3

5 10000
1 2 3 4 5

Sample Output 3

586965467

Problem Statement

You are in a store to buy N items. The regular price of the i-th item is P_i yen (the currency in Japan).

You have M coupons. You can use the i-th coupon to buy an item whose regular price is at least L_i yen at a D_i-yen discount.

Here, each coupon can be used only once. Besides, multiple coupons cannot be used for the same item.

If no coupon is used for an item, you will buy it for a regular price. Find the minimum possible total amount of money required to buy all the N items.

Constraints

• 1\leq N,M\leq 2\times 10^5
• 1\leq P_i\leq 10^9
• 1\leq D_i \leq L_i \leq 10^9
• All input values are integers.

Sample Input 1

3 3
4 3 1
4 4 2
2 3 1

Sample Output 1

4

Consider using the 2-nd coupon for the 1-st item, and the 3-rd coupon for the 2-nd item.

Then, you buy the 1-st item for 4-3=1 yen, 2-nd item for 3-1=2 yen, and 3-rd item for 1 yen. Thus, you can buy all the items for 1+2+1=4 yen.

Sample Input 2

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

Sample Output 2

37