Problem Statement

You are given a string S consisting of lowercase English letters.

Swap the a-th and b-th characters from the beginning of S and print the resulting string.

Constraints

• S is a string consisting of lowercase English letters.
• The length of S, |S|, satisfies 2 \leq |S| \leq 10.
• 1 \leq a < b \leq |S|
• a and b are integers.

Sample Input 1

chokudai
3 5

Sample Output 1

chukodai

After swapping the 3-rd character o and 5-th character u of chokudai, we have chukodai.

Sample Input 2

aa
1 2

Sample Output 2

aa

In this sample, after swapping the 1-st and 2-nd characters of S, we have the same string as S.

Sample Input 3

aaaabbbb
1 8

Sample Output 3

baaabbba

Problem Statement

There was an exam consisting of three problems worth 1, 2, and 4 points.

Takahashi, Aoki, and Snuke took this exam. Takahashi scored A points, and Aoki scored B points.

Snuke solved all of the problems solved by at least one of Takahashi and Aoki, and failed to solve any of the problems solved by neither of them.

Find Snuke's score.

It can be proved that Snuke's score is uniquely determined under the Constraints of this problem.

Constraints

• 0\leq A,B \leq 7
• A and B are integers.

Sample Input 1

1 2

Sample Output 1

3

Since Takahashi scored 1 point, we see that he solved only the 1-point problem and failed to solve the other two.
Similarly, since Aoki scored 2 points, we see that he solved only the 2-point problem and failed to solve the other two.

Therefore, Snuke must have solved the 1- and 2-point problems, but not the 4-point one, which Takahashi and Aoki both failed to solve, for a score of 3 points. Thus, 3 should be printed.

Sample Input 2

5 3

Sample Output 2

7

Since Takahashi scored 5 points, we see that he solved the 1- and 4-point problems but not the 2-point one.
Similarly, since Aoki scored 3 points, we see that he solved the 1- and 2-point problems but not the 4-point one.

Therefore, each of the three problems is solved by at least one of Takahashi and Aoki, so we see that Snuke solved all of the problems, for a score of 7 points. Thus, 7 should be printed.

Sample Input 3

0 0

Sample Output 3

0

Both Takahashi and Aoki solved none of the problems. Therefore, so did Snuke. Thus, 0 should be printed.

Problem Statement

There are N sequences of integers.
The i-th (1 \leq i \leq N) sequence has L_i terms; the j-th (1 \leq j \leq L_i) term of the i-th sequence is a_{i, j}.

You are given Q queries. For the k-th (1 \leq k \leq Q) query, given integers s_k and t_k, find the t_k-th term of the s_k-th sequence.

Constraints

• 1 \leq N, Q \leq 2 \times 10^5
• L_i \geq 1 \, (1 \leq i \leq N)
• \sum_{i=1}^N L_i \leq 2 \times 10^5
• 1 \leq a_{i, j} \leq 10^9 \, (1 \leq i \leq N, 1 \leq j \leq L_i)
• 1 \leq s_k \leq N, 1 \leq t_k \leq L_{s_k} \, (1 \leq k \leq Q)
• All values in the input are integers.

Sample Input 1

2 2
3 1 4 7
2 5 9
1 3
2 1

Sample Output 1

7
5

The 1-st sequence is (1, 4, 7) and the 2-nd is (5, 9).
The answer to each query is as follows:

• The 3-rd term of the 1-st sequence is 7.
• The 1-st term of the 2-nd sequence is 5.

Sample Input 2

3 4
4 128 741 239 901
2 1 1
3 314 159 26535
1 1
2 2
3 3
1 4

Sample Output 2

128
1
26535
901

Problem Statement

There are N people numbered 1,2,\ldots,N.

M parties were held. k_i people attended the i-th (1\leq i \leq M) party, and they were People x_{i,1},x_{i,2},\ldots,x_{i,k_i}.

Determine if every two people attended the same party at least once.

Constraints

• 2\leq N \leq 100
• 1\leq M \leq 100
• 2\leq k_i \leq N
• 1\leq x_{i,1}<x_{i,2}<\ldots < x_{i,k_i}\leq N
• All values in the input are integers.

Sample Input 1

3 3
2 1 2
2 2 3
2 1 3

Sample Output 1

Yes

Both Person 1 and Person 2 attended the 1-st party.

Both Person 2 and Person 3 attended the 2-nd party.

Both Person 1 and Person 3 attended the 3-rd party.

Therefore, every two people attended the same party at least once, so the answer is Yes.

Sample Input 2

4 2
3 1 2 4
3 2 3 4

Sample Output 2

No

Person 1 and Person 3 did not attend the same party, so the answer is No.

Problem Statement

There is a class with N students. The height of the i-th student (1 \leq i \leq N) is A_i.

For each j=1,2,\ldots,Q, answer the following question.

• How many of the N students have a height of at least x_j?

Constraints

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

Sample Input 1

3 1
100 160 130
120

Sample Output 1

2

The students with a height of at least 120 are the 2-nd and 3-rd ones.

Sample Input 2

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

Sample Output 2

0
1
2
3
4

Sample Input 3

5 5
804289384 846930887 681692778 714636916 957747794
424238336
719885387
649760493
596516650
189641422

Sample Output 3

5
3
5
5
5

Problem Statement

Given an integer N, solve the following problem.

Let f(x)= (The number of positive integers at most x with the same number of digits as x).
Find f(1)+f(2)+\dots+f(N) modulo 998244353.

Constraints

• N is an integer.
• 1 \le N < 10^{18}

Sample Input 1

16

Sample Output 1

73

• For a positive integer x between 1 and 9, the positive integers at most x with the same number of digits as x are 1,2,\dots,x.
  • Thus, we have f(1)=1,f(2)=2,...,f(9)=9.
• For a positive integer x between 10 and 16, the positive integers at most x with the same number of digits as x are 10,11,\dots,x.
  • Thus, we have f(10)=1,f(11)=2,...,f(16)=7.

The final answer is 73.

Sample Input 2

238

Sample Output 2

13870

Sample Input 3

999999999999999999

Sample Output 3

762062362

Be sure to find the sum modulo 998244353.

Problem Statement

You are given an 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.

Determine whether every connected component in this graph satisfies the following condition.

• The connected component has the same number of vertices and edges.

Notes

An undirected graph is a graph with edges without direction.
A subgraph of a graph is a graph formed from a subset of vertices and edges of that graph.
A graph is connected when one can travel between every pair of vertices in the graph via edges.
A connected component is a connected subgraph that is not part of any larger connected subgraph.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 2 \times 10^5
• 1 \leq u_i \leq v_i \leq N
• All values in the input are integers.

Sample Input 1

3 3
2 3
1 1
2 3

Sample Output 1

Yes

The graph has a connected component formed from just vertex 1, and another formed from vertices 2 and 3.
The former has one edge (edge 2), and the latter has two edges (edges 1 and 3), satisfying the condition.

Sample Input 2

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

Sample Output 2

Yes

Sample Input 3

13 16
7 9
7 11
3 8
1 13
11 11
6 11
8 13
2 11
3 3
8 12
9 11
1 11
5 13
3 12
6 9
1 10

Sample Output 3

No

Problem Statement

There is a family consisting of person 1, person 2, \ldots, and person N. For i\geq 2, person i's parent is person p_i.

They bought insurance M times. For i=1,2,\ldots,M, person x_i bought the i-th insurance, which covers that person and their descendants in the next y_i generations.

How many people are covered by at least one insurance?

Constraints

• 2 \leq N \leq 3 \times 10^5
• 1 \leq M \leq 3 \times 10^5
• 1 \leq p_i \leq i-1
• 1 \leq x_i \leq N
• 1 \leq y_i \leq 3 \times 10^5
• All input values are integers.

Sample Input 1

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

Sample Output 1

4

The 1-st insurance covers people 1, 2, and 4, because person 1's 1-st generation descendants are people 2 and 4.
The 2-nd insurance covers people 1, 2, 3, and 4, because person 1's 1-st generation descendants are people 2 and 4, and person 1's 2-nd generation descendant is person 3.
The 3-rd insurance covers person 4, because person 4 has no 1-st, 2-nd, or 3-rd descendants.

Therefore, four people, people 1, 2, 3, and 4, are covered by at least one insurance.

Sample Input 2

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

Sample Output 2

10

Problem Statement

There are 2N students standing in a row, numbered 1, 2, \ldots, 2N from left to right. For all pairs of two students, they are on good or bad terms. Specifically, for each 1\leq i\leq M, Student A_i and Student B_i are on good terms; for the remaining pairs of two students, they are on bad terms.

The teacher is going to do the following operation N times to form N pairs of two students.

• Choose two adjacent students who are on good terms, pair them, and remove them from the row.
• If the removed students were not at an end of the row, close up the gap so that the two students who were to the left and right of the removed students are now adjacent.

Find the number, modulo 998244353, of possible ways to do the operation N times. Two ways to do the operation N times are considered different when there exists 1\leq i\leq N such that the pair of students chosen in the i-th operation is different in those two ways.

Constraints

• 1 \leq N \leq 200
• 0 \leq M \leq N(2N-1)
• 1 \leq A_i < B_i \leq 2N
• All pairs (A_i, B_i) are distinct.
• All values in input are integers.

Sample Input 1

2 3
1 2
1 4
2 3

Sample Output 1

1

The only way to complete the procedure is to choose Students 2 and 3 in the first and Students 1 and 4 in the second. If Students 1 and 2 are chosen in the first operation, Students 3 and 4 will remain, who are on bad terms and thus cannot be paired in the second operation.
Thus, you should print 1.

Sample Input 2

2 2
1 2
3 4

Sample Output 2

2

There are two ways to complete the procedure: one way is to choose Students 1 and 2 in the first operation and Students 3 and 4 in the second, and the other way is to choose Students 3 and 4 in the first operation and Students 1 and 2 in the second. Note that these two ways are distinguished.

Sample Input 3

2 2
1 3
2 4

Sample Output 3

0

Since no pair can be chosen in the first operation, there is no way to complete the procedure, so you should print 0.