Problem Statement

You are given a string S ending with er or ist.
If S ends with er, print er; if it ends with ist, print ist.

Constraints

• 2 \le |S| \le 20
• S consists of lowercase English letters.
• S ends with er or ist.

Sample Input 1

atcoder

Sample Output 1

er

S="atcoder" ends with er.

Sample Input 2

tourist

Sample Output 2

ist

Sample Input 3

er

Sample Output 3

er

Problem Statement

You are given a string S consisting of uppercase and lowercase English letters.
Here, exactly one character of S is uppercase, and the others are all lowercase.
Find the integer x such that the x-th character of S is uppercase.
Here, the initial character of S is considered the 1-st one.

Constraints

• S is a string of length between 2 and 100, inclusive, consisting of uppercase and lowercase English letters.
• S has exactly one uppercase letter.

Sample Input 1

aBc

Sample Output 1

2

The 1-st character of aBc is a, the 2-nd is B, and the 3-rd is c; the 2-nd character is uppercase.
Thus, 2 should be printed.

Sample Input 2

xxxxxxXxxx

Sample Output 2

7

An uppercase letter X occurs as the 7-th character of S=xxxxxxXxxx, so 7 should be printed.

Sample Input 3

Zz

Sample Output 3

1

Problem Statement

Let us call a string consisting of uppercase and lowercase English alphabets a wonderful string if all of the following conditions are satisfied:

• The string contains an uppercase English alphabet.
• The string contains a lowercase English alphabet.
• All characters in the string are pairwise distinct.

For example, AtCoder and Aa are wonderful strings, while atcoder and Perfect are not.

Given a string S, determine if S is a wonderful string.

Constraints

• 1 \le |S| \le 100
• S is a string consisting of uppercase and lowercase English alphabets.

Sample Input 1

AtCoder

Sample Output 1

Yes

AtCoder is a wonderful string because it contains an uppercase English alphabet, a lowercase English alphabet, and all characters in the string are pairwise distinct.

Sample Input 2

Aa

Sample Output 2

Yes

Note that A and a are different characters. This string is a wonderful string.

Sample Input 3

atcoder

Sample Output 3

No

It is not a wonderful string because it does not contain an uppercase English alphabet.

Sample Input 4

Perfect

Sample Output 4

No

It is not a wonderful string because the 2-nd and the 5-th characters are the same.

Problem Statement

Takahashi is exploring a cave in a video game.

The cave consists of N rooms arranged in a row. The rooms are numbered Room 1,2,\ldots,N from the entrance.

Takahashi is initially in Room 1, and the time limit is T.
For each 1 \leq i \leq N-1, he may consume a time of A_i to move from Room i to Room (i+1). There is no other way to move between rooms. He cannot make a move that makes the time limit 0 or less.

There are M bonus rooms in the cave. The i-th bonus room is Room X_i; when he arrives at the room, the time limit increases by Y_i.

Can Takahashi reach Room N?

Constraints

• 2 \leq N \leq 10^5
• 0 \leq M \leq N-2
• 1 \leq T \leq 10^9
• 1 \leq A_i \leq 10^9
• 1 < X_1 < \ldots < X_M < N
• 1 \leq Y_i \leq 10^9
• All values in input are integers.

Sample Input 1

4 1 10
5 7 5
2 10

Sample Output 1

Yes

• Takahashi is initially in Room 1, and the time limit is 10.
• He consumes a time of 5 to move to Room 2. Now the time limit is 5. Then, the time limit increases by 10; it is now 15.
• He consumes a time of 7 to move to Room 3. Now the time limit is 8.
• He consumes a time of 5 to move to Room 4. Now the time limit is 3.

Sample Input 2

4 1 10
10 7 5
2 10

Sample Output 2

No

He cannot move from Room 1 to Room 2.

Problem Statement

You are given a sequence A=(A_1,A_2,\ldots,A_N) of length N consisting of non-negative integers.

Determine if there is an even number represented as the sum of two different elements of A. If it exists, find the maximum such number.

Constraints

• 2\leq N \leq 2\times 10^5
• 0\leq A_i\leq 10^9
• The elements of A are distinct.
• All values in the input are integers.

Sample Input 1

3
2 3 4

Sample Output 1

6

The values represented as the sum of two distinct elements of A are 5, 6, and 7. We have an even number here, and the maximum is 6.

Sample Input 2

2
1 0

Sample Output 2

-1

The value represented as the sum of two distinct elements of A is 1. We have no even number here, so -1 should be printed.

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.
Find the number of connected components in this graph.

Notes

A simple undirected graph is a graph that is simple and has undirected edges.
A graph is simple if and only if it has no self-loop or multi-edge.

A subgraph of a graph is a graph formed from some of the vertices and edges of that graph.
A graph is connected if and only if one can travel between every pair of vertices via edges.
A connected component is a connected subgraph that is not part of any larger connected subgraph.

Constraints

• 1 \leq N \leq 100
• 0 \leq M \leq \frac{N(N - 1)}{2}
• 1 \leq u_i, v_i \leq N
• The given graph is simple.
• All values in the input are integers.

Sample Input 1

5 3
1 2
1 3
4 5

Sample Output 1

2

The given graph contains the following two connected components:

• a subgraph formed from vertices 1, 2, 3, and edges 1, 2;
• a subgraph formed from vertices 4, 5, and edge 3.

Sample Input 2

5 0

Sample Output 2

5

Sample Input 3

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

Sample Output 3

1

Problem Statement

We have 2N balls. Each ball has a color represented by an integer between 1 and N (inclusive). For each of the N colors, there are exactly two balls of that color.

These balls are contained in M cylinders placed perpendicularly to the floor. Initially, the i-th cylinder (1 \leq i \leq M) contains k_i balls, the j-th of which from the top (1 \leq j \leq k_i) has the color a_{i, j}.

Your objective is to empty all M cylinders by repeating the following operation.

• Choose two different non-empty cylinders and remove the topmost ball from each of them. Here, the two balls removed must be of the same color.

Determine whether the objective is achievable.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 2 \leq M \leq 2 \times 10^5
• 1 \leq k_i\ (1 \leq i \leq M)
• 1 \leq a_{i,j} \leq N\ (1 \leq i \leq M,1 \leq j \leq k_i)
• \sum_{i=1}^{M} k_i = 2N
• For every x\ (1 \leq x \leq N), there exists exactly two pairs of integers (i,j) such that 1 \leq i \leq M, 1 \leq j \leq k_i, and a_{i,j}=x.
• All values in input are integers.

Sample Input 1

2 2
2
1 2
2
1 2

Sample Output 1

Yes

The objective can be achieved as follows.

1. Choose the first and second cylinders to remove the topmost ball from each of them, which is allowed since the removed balls have the same color: 1.
2. Choose the first and second cylinders to remove the topmost ball from each of them, which is allowed since the removed balls have the same color: 2.

Sample Input 2

2 2
2
1 2
2
2 1

Sample Output 2

No

No operation can be done at all, which means it is impossible to achieve the objective of emptying the M cylinders.

Problem Statement

Given is a sequence of N integers: A = (A_1, A_2, \dots, A_N).

Find the number of (not necessarily contiguous) subsequences A'=(A'_1,A'_2,\ldots,A'_k) of length at least 2 that satisfy the following condition:

• A'_1 \leq A'_k.

Since the count can be enormous, print it modulo 998244353.

Here, two subsequences are distinguished when they originate from different sets of indices, even if they are the same as sequences.

Constraints

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

Sample Input 1

3
1 2 1

Sample Output 1

3

A=(1,2,1) has four (not necessarily contiguous) subsequences of length at least 2: (1,2), (1,1), (2,1), (1,2,1).

Three of them, (1,2), (1,1), (1,2,1), satisfy the condition in Problem Statement.

Sample Input 2

3
1 2 2

Sample Output 2

4

Note that two subsequences are distinguished when they originate from different sets of indices, even if they are the same as sequences.

In this Sample, there are four subsequences, (1,2), (1,2), (2,2), (1,2,2), that satisfy the condition.

Sample Input 3

3
3 2 1

Sample Output 3

0

There may be no subsequence that satisfies the condition.

Sample Input 4

10
198495780 28463047 859606611 212983738 946249513 789612890 782044670 700201033 367981604 302538501

Sample Output 4

830

Problem Statement

We have a loaf of bread of length L, which we will cut and distribute to N children.
The i-th child (1\leq i\leq N) wants a loaf of length A_i.

Now, Takahashi will repeat the operation below to cut the loaf into lengths A_1, A_2, \ldots, A_N for the children.

Choose a loaf of length k and an integer x between 1 and k-1 (inclusive). Cut the loaf into two loaves of length x and k-x.
This operation incurs a cost of k regardless of the value of x.

Each child i must receive a loaf of length exactly A_i, but it is allowed to leave some loaves undistributed.

Find the minimum cost needed to distribute loaves to all children.

Constraints

• 2 \leq N \leq 2\times 10^5
• 1\leq A_i\leq 10^9
• A_1+A_2+\cdots+A_N\leq L\leq 10^{15}
• All values in input are integers.

Sample Input 1

5 7
1 2 1 2 1

Sample Output 1

16

Takahashi can cut the loaf for the children as follows.

• Choose the loaf of length 7 and x=3, cutting it into loaves of length 3 and 4 for a cost of 7.
• Choose the loaf of length 3 and x=1, cutting it into loaves of length 1 and 2 for a cost of 3. Give the former to the 1-st child.
• Choose the loaf of length 2 and x=1, cutting it into two loaves of length 1 for a cost of 2. Give them to the 3-rd and 5-th children.
• Choose the loaf of length 4 and x=2, cutting it into two loaves of length 2 for a cost of 4. Give them to the 2-nd and 4-th children.

This incurs a cost of 7+3+2+4=16, which is the minimum possible. There will be no leftover loaves.

Sample Input 2

3 1000000000000000
1000000000 1000000000 1000000000

Sample Output 2

1000005000000000

Note that each child i must receive a loaf of length exactly A_i.