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

You are given three integers A,B,C. Determine whether it is possible to divide these three integers into two or more groups so that these groups have equal sums.

Constraints

• 1 \leq A,B,C \leq 1000
• All input values are integers.

Sample Input 1

3 8 5

Sample Output 1

Yes

For example, by dividing into two groups (3,5) and (8), each group can have the sum 8.

Sample Input 2

2 2 2

Sample Output 2

Yes

By dividing into three groups (2),(2),(2), each group can have the sum 2.

Sample Input 3

1 2 4

Sample Output 3

No

No matter how you divide them into two or more groups, it is not possible to make the sums equal.

Problem Statement

You are given a string S consisting of lowercase English letters. Find the character that appears most frequently in S. If multiple such characters exist, report the one that comes earliest in alphabetical order.

Constraints

• 1 \leq |S| \leq 1000 (|S| is the length of the string S.)
• Each character in S is a lowercase English letter.

Sample Input 1

frequency

Sample Output 1

e

In frequency, the letter e appears twice, which is more than any other character, so you should print e.

Sample Input 2

atcoder

Sample Output 2

a

In atcoder, each of the letters a, t, c, o, d, e, and r appears once, so you should print the earliest in alphabetical order, which is a.

Sample Input 3

pseudopseudohypoparathyroidism

Sample Output 3

o

Problem Statement

In AtCoder City, N types of garbage are collected regularly. The i-th type of garbage (i=1,2,\dots,N) is collected on days when the date modulo q_i equals r_i.

Answer Q queries. In the j-th query (j=1,2,\dots,Q), given that the t_j-th type of garbage is put out on day d_j, answer the next day on which it will be collected.

Here, if the i-th type of garbage is put out on a day when that type of garbage is collected, then the garbage will be collected on the same day.

Constraints

• 1 \leq N \leq 100
• 0 \leq r_i < q_i \leq 10^9
• 1 \leq Q \leq 100
• 1 \leq t_j \leq N
• 1 \leq d_j \leq 10^9
• All input values are integers.

Sample Input 1

2
7 3
4 2
5
1 1
1 3
1 4
1 15
2 7

Sample Output 1

3
3
10
17
10

• 1st query: The 1st type of garbage is collected on day 3 for the first time after day 1.
• 2nd query: The 1st type of garbage is collected on day 3 for the first time after day 3.
• 3rd query: The 1st type of garbage is collected on day 10 for the first time after day 4.

Problem Statement

You are given two sequences, each of length N, consisting of integers: A=(A_1, \ldots, A_N) and B=(B_1, \ldots, B_N).

Determine whether there is a sequence of length N, X=(X_1, \ldots, X_N), satisfying all of the conditions below.

• X_i = A_i or X_i = B_i, for every i(1\leq i\leq N).

• |X_i - X_{i+1}| \leq K, for every i(1\leq i\leq N-1).

Constraints

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

Sample Input 1

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

Sample Output 1

Yes

X=(9,6,3,7,5) satisfies all conditions.

Sample Input 2

4 90
1 1 1 100
1 2 3 100

Sample Output 2

No

No X satisfies all conditions.

Sample Input 3

4 1000000000
1 1 1000000000 1000000000
1 1000000000 1 1000000000

Sample Output 3

Yes

Problem Statement

You are given N strings S_1,S_2,\dots,S_N, each of length M, consisting of lowercase English letter. Here, S_i are pairwise distinct.

Determine if one can rearrange these strings to obtain a new sequence of strings T_1,T_2,\dots,T_N such that:

• for all integers i such that 1 \le i \le N-1, one can alter exactly one character of T_i to another lowercase English letter to make it equal to T_{i+1}.

Constraints

• 2 \le N \le 8
• 1 \le M \le 5
• S_i is a string of length M consisting of lowercase English letters. (1 \le i \le N)
• S_i are pairwise distinct.

Sample Input 1

4 4
bbed
abcd
abed
fbed

Sample Output 1

Yes

One can rearrange them in this order: abcd, abed, bbed, fbed. This sequence satisfies the condition.

Sample Input 2

2 5
abcde
abced

Sample Output 2

No

No matter how the strings are rearranged, the condition is never satisfied.

Sample Input 3

8 4
fast
face
cast
race
fact
rice
nice
case

Sample Output 3

Yes

Problem Statement

Initially, there are N sizes of slimes.
Specifically, for each 1\leq i\leq N, there are C_i slimes of size S_i.

Takahashi can repeat slime synthesis any number of times (possibly zero) in any order.
Slime synthesis is performed as follows.

• Choose two slimes of the same size. Let this size be X, and a new slime of size 2X appears. Then, the two original slimes disappear.

Takahashi wants to minimize the number of slimes. What is the minimum number of slimes he can end up with by an optimal sequence of syntheses?

Constraints

• 1\leq N\leq 10^5
• 1\leq S_i\leq 10^9
• 1\leq C_i\leq 10^9
• S_1,S_2,\ldots,S_N are all different.
• All input values are integers.

Sample Input 1

3
3 3
5 1
6 1

Sample Output 1

3

Initially, there are three slimes of size 3, one of size 5, and one of size 6.
Takahashi can perform the synthesis twice as follows:

• First, perform the synthesis by choosing two slimes of size 3. There will be one slime of size 3, one of size 5, and two of size 6.
• Next, perform the synthesis by choosing two slimes of size 6. There will be one slime of size 3, one of size 5, and one of size 12.

No matter how he repeats the synthesis from the initial state, he cannot reduce the number of slimes to 2 or less, so you should print 3.

Sample Input 2

3
1 1
2 1
3 1

Sample Output 2

3

He cannot perform the synthesis.

Sample Input 3

1
1000000000 1000000000

Sample Output 3

13

Problem Statement

You are given a simple undirected graph with N vertices numbered 1 to N and M edges numbered 1 to M. Edge i connects vertex u_i and vertex v_i. The degree of each vertex is at most 10.
Let K be the number of simple paths (paths without repeated vertices) starting from vertex 1. Print \min(K, 10^6).

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq \min \left(2 \times 10^5, \frac{N(N-1)}{2}\right)
• 1 \leq u_i, v_i \leq N
• The given graph is simple.
• The degree of each vertex in the given graph is at most 10.
• All values in the input are integers.

Sample Input 1

4 2
1 2
2 3

Sample Output 1

3

We have the following three paths that count. (Note that a path of length 0 also counts.)

• Vertex 1;
• vertex 1, vertex 2;
• vertex 1, vertex 2, vertex 3.

Sample Input 2

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

Sample Output 2

16

Sample Input 3

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

Sample Output 3

2023

Problem Statement

There are N rooms numbered 1, 2, \ldots, N, each with one person living in it, and M corridors connecting two different rooms. The i-th corridor connects room U_i and room V_i with a length of W_i.

One day (we call this day 0), the K people living in rooms A_1, A_2, \ldots, A_K got (newly) infected with a virus. Furthermore, on the i-th of the following D days (1\leq i\leq D), the infection spread as follows.

People who were infected at the end of the night of day (i-1) remained infected at the end of the night of day i.
For those who were not infected, they were newly infected if and only if they were living in a room within a distance of X_i from at least one room where an infected person was living at the end of the night of day (i-1). Here, the distance between rooms P and Q is defined as the minimum possible sum of the lengths of the corridors when moving from room P to room Q using only corridors. If it is impossible to move from room P to room Q using only corridors, the distance is set to 10^{100}.

For each i (1\leq i\leq N), print the day on which the person living in room i was newly infected. If they were not infected by the end of the night of day D, print -1.

Constraints

• 1 \leq N\leq 3\times 10^5
• 0 \leq M\leq 3\times 10^5
• 1 \leq U_i < V_i\leq N
• All (U_i,V_i) are different.
• 1\leq W_i\leq 10^9
• 1 \leq K\leq N
• 1\leq A_1<A_2<\cdots<A_K\leq N
• 1 \leq D\leq 3\times 10^5
• 1\leq X_i\leq 10^9
• All input values are integers.

Sample Input 1

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

Sample Output 1

0
1
1
2

The infection spreads as follows.

• On the night of day 0, the person living in room 1 gets infected.
• The distances between room 1 and rooms 2,3,4 are 2,3,5, respectively. Thus, since X_1=3, the people living in rooms 2 and 3 are newly infected on the night of day 1.
• The distance between rooms 3 and 4 is 2. Thus, since X_2=3, the person living in room 4 also gets infected on the night of day 2.

Therefore, the people living in rooms 1,2,3,4 were newly infected on days 0,1,1,2, respectively, so print 0,1,1,2 in this order on separate lines.

Sample Input 2

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

Sample Output 2

0
1
2
-1
2
0
-1

Sample Input 3

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

Sample Output 3

0
2
0
-1
-1

Note that it is not always possible to move between any two rooms using only corridors.