Problem Statement

Takahashi turns on the light of his room at S o'clock (on the 24-hour clock) every day and turns it off at T o'clock every day.
The date may change while the light is on.

Determine whether the light is on at 30 minutes past X o'clock.

Constraints

• 0 \leq S, T, X \leq 23
• S \neq T
• All values in input are integers.

Sample Input 1

7 20 12

Sample Output 1

Yes

The light is on between 7 o'clock and 20 o'clock. At 30 minutes past 12 o'clock, it is on, so we print Yes.

Sample Input 2

20 7 12

Sample Output 2

No

The light is on between 0 o'clock and 7 o'clock, and between 20 o'clock and 0 o'clock (on the next day). At 30 minutes past 12 o'clock, it is off, so we print No.

Sample Input 3

23 0 23

Sample Output 3

Yes

Problem Statement

Takahashi's purse has one or more 100-yen coins in it and nothing else. (Yen is the Japanese currency.)

Is it possible that the total amount of money in the purse is X yen?

Constraints

• 0 \leq X \leq 1000
• All values in input are integers.

Sample Input 1

500

Sample Output 1

Yes

If the purse has five 100-yen coins, the total amount of money is 500 yen. Thus, it is possible that the total amount is X=500 yen, so we should print Yes.

Sample Input 2

40

Sample Output 2

No

Sample Input 3

0

Sample Output 3

No

Note that the purse has at least one 100-yen coin.

Problem Statement

Takahashi has a piano with 100 keys arranged in a row. The i-th key from the left is called key i.

He will play music by pressing N keys one by one. For the i-th press, he will press key A_i, using his left hand if S_i= L, and his right hand if S_i= R.

Before starting to play, he can place both of his hands on any keys he likes, and his fatigue level at this point is 0. During the performance, if he moves one hand from key x to key y, the fatigue level increases by |y-x| (conversely, the fatigue level does not increase for any reason other than moving hands). To press a certain key with a hand, that hand must be placed on that key.

Find the minimum possible fatigue level at the end of the performance.

Constraints

• 1 \leq N \leq 100
• 1 \leq A_i \leq 100
• N and A_i are integers.
• S_i is L or R.

Sample Input 1

4
3 L
6 R
9 L
1 R

Sample Output 1

11

For example, the performance can be done as follows:

• Initially, place the left hand on key 3 and the right hand on key 6.
• Press key 3 with the left hand.
• Press key 6 with the right hand.
• Move the left hand from key 3 to key 9. The fatigue level increases by |9-3| = 6.
• Move the right hand from key 6 to key 1. The fatigue level increases by |1-6| = 5.
• Press key 9 with the left hand.
• Press key 1 with the right hand.

In this case, the fatigue level at the end of the performance is 6+5 = 11, which is the minimum possible.

Sample Input 2

3
2 L
2 L
100 L

Sample Output 2

98

Sample Input 3

8
22 L
75 L
26 R
45 R
72 R
81 R
47 L
29 R

Sample Output 3

188

Problem Statement

You are given a string S consisting of lowercase English letters. How many different non-empty substrings does S have?

A substring is a contiguous subsequence. For example, xxx is a substring of yxxxy but not of xxyxx.

Constraints

• S is a string of length between 1 and 100, inclusive, consisting of lowercase English letters.

Sample Input 1

yay

Sample Output 1

5

S has the following five different non-empty substrings:

• a
• y
• ay
• ya
• yay

Sample Input 2

aababc

Sample Output 2

17

Sample Input 3

abracadabra

Sample Output 3

54

Problem Statement

You are given N pairs of integers (L_1, R_1), (L_2, R_2), \ldots, (L_N, R_N).

Determine whether there exists a sequence of N integers X = (X_1, X_2, \ldots, X_N) that satisfies the following conditions, and print one such sequence if it exists.

• L_i \leq X_i \leq R_i for each i = 1, 2, \ldots, N.
• \displaystyle \sum_{i=1}^N X_i = 0.

Constraints

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

Sample Input 1

3
3 5
-4 1
-2 3

Sample Output 1

Yes
4 -3 -1

The sequence X = (4, -3, -1) satisfies all the conditions. Other valid sequences include (3, -3, 0) and (5, -4, -1).

Sample Input 2

3
1 2
1 2
1 2

Sample Output 2

No

No sequence X satisfies the conditions.

Sample Input 3

6
-87 12
-60 -54
2 38
-76 6
87 96
-17 38

Sample Output 3

Yes
-66 -57 31 -6 89 9

Problem Statement

Print all integer sequences of length N that satisfy the following conditions, in ascending lexicographical order.

• The i-th element is between 1 and R_i, inclusive.
• The sum of all elements is a multiple of K.

Constraints

• All input values are integers.
• 1 \le N \le 8
• 2 \le K \le 10
• 1 \le R_i \le 5

Sample Input 1

3 2
2 1 3

Sample Output 1

1 1 2
2 1 1
2 1 3

There are three sequences to be printed, which are (1,1,2),(2,1,1),(2,1,3) in lexicographical order.

Sample Input 2

1 2
1

Sample Output 2

There may be no sequences to print.
In this case, the output can be empty.

Sample Input 3

5 5
2 3 2 3 2

Sample Output 3

1 1 1 1 1
1 2 2 3 2
1 3 1 3 2
1 3 2 2 2
1 3 2 3 1
2 1 2 3 2
2 2 1 3 2
2 2 2 2 2
2 2 2 3 1
2 3 1 2 2
2 3 1 3 1
2 3 2 1 2
2 3 2 2 1

Problem Statement

A string consisting of lowercase English letters, (, and ) is said to be a good string if you can make it an empty string by the following procedure:

• First, remove all lowercase English letters.
• Then, repeatedly remove consecutive () while possible.

For example, ((a)ba) is a good string, because removing all lowercase English letters yields (()), from which we can remove consecutive () at the 2-nd and 3-rd characters to obtain (), which in turn ends up in an empty string.

You are given a good string S. We denote by S_i the i-th character of S.

For each lowercase English letter a, b, \ldots, and z, we have a ball with the letter written on it. Additionally, we have an empty box.

For each i = 1,2, \ldots ,|S| in this order, Takahashi performs the following operation unless he faints.

• If S_i is a lowercase English letter, put the ball with the letter written on it into the box. If the ball is already in the box, he faints.
• If S_i is (, do nothing.
• If S_i is ), take the maximum integer j less than i such that the j-th through i-th characters of S form a good string. (We can prove that such an integer j always exists.) Take out from the box all the balls that he has put in the j-th through i-th operations.

Determine if Takahashi can complete the sequence of operations without fainting.

Constraints

• 1 \leq |S| \leq 3 \times 10^5
• S is a good string.

Sample Input 1

((a)ba)

Sample Output 1

Yes

For i = 1, he does nothing.
For i = 2, he does nothing.
For i = 3, he puts the ball with a written on it into the box.
For i = 4, j=2 is the maximum integer less than 4 such that the j-th through 4-th characters of S form a good string, so he takes out the ball with a written on it from the box.
For i = 5, he puts the ball with b written on it into the box.
For i = 6, he puts the ball with a written on it into the box.
For i = 7, j=1 is the maximum integer less than 7 such that the j-th through 7-th characters of S form a good string, so he takes out the ball with a written on it, and another with b, from the box.

Therefore, the answer to this case is Yes.

Sample Input 2

(a(ba))

Sample Output 2

No

For i = 1, he does nothing.
For i = 2, he puts the ball with a written on it into the box.
For i = 3, he does nothing.
For i = 4, he puts the ball with b written on it into the box.
For i = 5, the ball with a written on it is already in the box, so he faints, aborting the sequence of operations.

Therefore, the answer to this case is No.

Sample Input 3

(((())))

Sample Output 3

Yes

Sample Input 4

abca

Sample Output 4

No

Problem Statement

We have a connected undirected graph with N vertices and M edges.
The vertices are numbered 1 through N, and the edges are numbered 1 through M. Edge i connects Vertices A_i and B_i.

Takahashi is going to remove zero or more edges from this graph.

When removing Edge i, a reward of C_i is given if C_i \geq 0, and a fine of |C_i| is incurred if C_i<0.

Find the maximum total reward that Takahashi can get when the graph must be connected after removing edges.

Constraints

• 2 \leq N \leq 2\times 10^5
• N-1 \leq M \leq 2\times 10^5
• 1 \leq A_i,B_i \leq N
• -10^9 \leq C_i \leq 10^9
• The given graph is connected.
• All values in input are integers.

Sample Input 1

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

Sample Output 1

4

Removing Edges 4 and 5 yields a total reward of 4. You cannot get any more, so the answer is 4.

Sample Input 2

3 3
1 2 1
2 3 0
3 1 -1

Sample Output 2

1

There may be edges that give a negative reward when removed.

Sample Input 3

2 3
1 2 -1
1 2 2
1 1 3

Sample Output 3

5

There may be multi-edges and self-loops.

Problem Statement

You are given a string S consisting of lowercase English letters. Print the number of non-empty strings T that satisfy the following condition, modulo 998244353.

The concatenation TT of two copies of T is a subsequence of S (not necessarily contiguous).

Constraints

• S is a string consisting of lowercase English letters whose length is between 1 and 100, inclusive.

Sample Input 1

ababbaba

Sample Output 1

8

The eight strings satisfying the condition are a, aa, ab, aba, b, ba, bab, and bb.

Sample Input 2

zzz

Sample Output 2

1

The only string satisfying the condition is z. Note that this string contributes to the answer just once, although there are three ways to extract the subsequence zz from S = S_1S_2S_3 = zzz: S_1S_2 = zz, S_1S_3 = zz, and S_2S_3 = zz.

Sample Input 3

ppppqqppqqqpqpqppqpqqqqpppqppq

Sample Output 3

580