Problem Statement

You are given N strings S_1,S_2,\ldots,S_N in this order.

Print S_N,S_{N-1},\ldots,S_1 in this order.

Constraints

• 1\leq N \leq 10
• N is an integer.
• S_i is a string of length between 1 and 10, inclusive, consisting of lowercase English letters, uppercase English letters, and digits.

Sample Input 1

3
Takahashi
Aoki
Snuke

Sample Output 1

Snuke
Aoki
Takahashi

We have N=3, S_1= Takahashi, S_2= Aoki, and S_3= Snuke.

Thus, you should print Snuke, Aoki, and Takahashi in this order.

Sample Input 2

4
2023
Year
New
Happy

Sample Output 2

Happy
New
Year
2023

The given strings may contain digits.

Problem Statement

You are given a string S of even length consisting of lowercase English letters. Let |S| be the length of S, and S_i be the i-th character of S.

Perform the following operation for each i = 1, 2, \ldots, \frac{|S|}{2} in this order, and print the final S.

• Swap S_{2i-1} and S_{2i}.

Constraints

• S is a string of even length consisting of lowercase English letters.
• The length of S is at most 100.

Sample Input 1

abcdef

Sample Output 1

badcfe

Initially, S = abcdef.
Performing the operation for i = 1 swaps S_1 and S_2, making S = bacdef.
Performing the operation for i = 2 swaps S_3 and S_4, making S = badcef.
Performing the operation for i = 3 swaps S_5 and S_6, making S = badcfe.
Thus, badcfe should be printed.

Sample Input 2

aaaa

Sample Output 2

aaaa

Sample Input 3

atcoderbeginnercontest

Sample Output 3

taocedbrgeniencrnoetts

Problem Statement

You are given strings S and T consisting of lowercase English letters. Determine whether T is a (contiguous) substring of S.

A string Y is said to be a (contiguous) substring of X if and only if Y can be obtained by performing the operation below on X zero or more times.

• Do one of the following.
  • Delete the first character in X.
  • Delete the last character in X.

For instance, tag is a (contiguous) substring of voltage, while ace is not a (contiguous) substring of atcoder.

Constraints

• S and T consist of lowercase English letters.
• 1 \le |S|,|T| \le 100 (|X| denotes the length of a string X.)

Sample Input 1

voltage
tag

Sample Output 1

Yes

tag is a (contiguous) substring of voltage.

Sample Input 2

atcoder
ace

Sample Output 2

No

ace is not a (contiguous) substring of atcoder.

Sample Input 3

gorilla
gorillagorillagorilla

Sample Output 3

No

Sample Input 4

toyotasystems
toyotasystems

Sample Output 4

Yes

It is possible that S=T.

Problem Statement

There are N players numbered 1 to N, who have played a round-robin tournament. For every match in this tournament, one player won and the other lost.

The results of the matches are given as N strings S_1,S_2,\ldots,S_N of length N each, in the following format:

• If i\neq j, the j-th character of S_i is o or x. o means that player i won against player j, and x means that player i lost to player j.

• If i=j, the j-th character of S_i is -.

The player with more wins ranks higher. If two players have the same number of wins, the player with the smaller player number ranks higher. Report the player numbers of the N players in descending order of rank.

Constraints

• 2\leq N\leq 100
• N is an integer.
• S_i is a string of length N consisting of o, x, and -.
• S_1,\ldots,S_N conform to the format described in the problem statement.

Sample Input 1

3
-xx
o-x
oo-

Sample Output 1

3 2 1

Player 1 has 0 wins, player 2 has 1 win, and player 3 has 2 wins. Thus, the player numbers in descending order of rank are 3,2,1.

Sample Input 2

7
-oxoxox
x-xxxox
oo-xoox
xoo-ooo
ooxx-ox
xxxxx-x
oooxoo-

Sample Output 2

4 7 3 1 5 2 6

Both players 4 and 7 have 5 wins, but player 4 ranks higher because their player number is smaller.

Problem Statement

We have a sequence of N numbers: A = (a_1, a_2, \dots, a_N).
Process the Q queries explained below.

• Query i: You are given a pair of integers (x_i, k_i). Let us look at the elements of A one by one from the beginning: a_1, a_2, \dots Which element will be the k_i-th occurrence of the number x_i?
  Print the index of that element, or -1 if there is no such element.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 0 \leq a_i \leq 10^9 (1 \leq i \leq N)
• 0 \leq x_i \leq 10^9 (1 \leq i \leq Q)
• 1 \leq k_i \leq N (1 \leq i \leq Q)
• All values in input are integers.

Sample Input 1

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

Sample Output 1

1
2
5
-1
3
6
-1
-1

1 occurs in A at a_1, a_2, a_5. Thus, the answers to Query 1 through 4 are 1, 2, 5, -1 in this order.

Sample Input 2

3 2
0 1000000000 999999999
1000000000 1
123456789 1

Sample Output 2

2
-1

Problem Statement

There are N sellers and M buyers in an apple market.

The i-th seller may sell an apple for A_i yen or more (yen is the currency in Japan).

The i-th buyer may buy an apple for B_i yen or less.

Find the minimum integer X that satisfies the following condition.

Condition: The number of people who may sell an apple for X yen is greater than or equal to the number of people who may buy an apple for X yen.

Constraints

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

Sample Input 1

3 4
110 90 120
100 80 120 10000

Sample Output 1

110

Two sellers, the 1-st and 2-nd, may sell an apple for 110 yen; two buyers, the 3-rd and 4-th, may buy an apple for 110 yen. Thus, 110 satisfies the condition.

Since an integer less than 110 does not satisfy the condition, this is the answer.

Sample Input 2

5 2
100000 100000 100000 100000 100000
100 200

Sample Output 2

201

Sample Input 3

3 2
100 100 100
80 120

Sample Output 3

100

Problem Statement

You are given a string S of length N consisting of uppercase and lowercase English letters.

Let us perform Q operations on the string S. The i-th operation (1\leq i\leq Q) is represented by a tuple (t _ i,x _ i,c _ i) of two integers and one character, as follows.

• If t _ i=1, change the x _ i-th character of S to c _ i.
• If t _ i=2, convert all uppercase letters in S to lowercase (do not use x _ i,c _ i for this operation).
• If t _ i=3, convert all lowercase letters in S to uppercase (do not use x _ i,c _ i for this operation).

Print the S after the Q operations.

Constraints

• 1\leq N\leq5\times10^5
• S is a string of length N consisting of uppercase and lowercase English letters.
• 1\leq Q\leq5\times10^5
• 1\leq t _ i\leq3\ (1\leq i\leq Q)
• If t _ i=1, then 1\leq x _ i\leq N\ (1\leq i\leq Q).
• c _ i is an uppercase or lowercase English letter.
• If t _ i\neq 1, then x _ i=0 and c _ i= 'a'.
• N,Q,t _ i,x _ i are all integers.

Sample Input 1

7
AtCoder
5
1 4 i
3 0 a
1 5 b
2 0 a
1 4 Y

Sample Output 1

atcYber

Initially, the string S is AtCoder.

• The first operation changes the 4-th character to i, changing S to AtCider.
• The second operation converts all lowercase letters to uppercase, changing S to ATCIDER.
• The third operation changes the 5-th character to b, changing S to ATCIbER.
• The fourth operation converts all uppercase letters to lowercase, changing S to atciber.
• The fifth operation changes the 4-th character to Y, changing S to atcYber.

After the operations, the string S is atcYber, so print atcYber.

Sample Input 2

35
TheQuickBrownFoxJumpsOverTheLazyDog
10
2 0 a
1 19 G
1 13 m
1 2 E
1 21 F
2 0 a
1 27 b
3 0 a
3 0 a
1 15 i

Sample Output 2

TEEQUICKBROWMFiXJUGPFOVERTBELAZYDOG

Problem Statement

Given is an undirected graph with N vertices and M edges.
Edge i connects Vertices A_i and B_i.

We will erase Vertices 1, 2, \ldots, N one by one.
Here, erasing Vertex i means deleting Vertex i and all edges incident to Vertex i from the graph.

For each i=1, 2, \ldots, N, how many connected components does the graph have when vertices up to Vertex i are deleted?

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq \min(\frac{N(N-1)}{2} , 2 \times 10^5 )
• 1 \leq A_i \lt B_i \leq N
• (A_i,B_i) \neq (A_j,B_j) if i \neq j.
• All values in input are integers.

Sample Input 1

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

Sample Output 1

1
2
3
2
1
0

The figure above shows the transition of the graph.

Sample Input 2

8 7
7 8
3 4
5 6
5 7
5 8
6 7
6 8

Sample Output 2

3
2
2
1
1
1
1
0

The graph may be disconnected from the beginning.

Problem Statement

You are given an integer sequence A = (A_1, A_2, \ldots, A_N) of length N.

We will perform the following operation on A for i = 1, 2, \ldots, M in this order.

• First, choose an integer between L_i and R_i, inclusive, uniformly at random and denote it as p.
• Then, change the value of A_p to the integer X_i.

For the final sequence A after the above procedure, print the expected value, modulo 998244353, of A_i for each i = 1, 2, \ldots, N.

Constraints

• All input values are integers.
• 1 \leq N, M \leq 2 \times 10^5
• 0 \leq A_i \leq 10^9
• 1 \leq L_i \leq R_i \leq N
• 0 \leq X_i \leq 10^9

Sample Input 1

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

Sample Output 1

499122179 1 665496238 665496236 5

We start from the initial state A = (3, 1, 4, 1, 5) and perform the following two operations.

• The first operation chooses A_1 or A_2 uniformly at random, and changes its value to 2.
• Then, the second operation chooses one of A_2, A_3, A_4 uniformly at random, and changes its value to 0.

As a result, the expected values of the elements in the final A are (E_1, E_2, E_3, E_4, E_5) = (\frac{5}{2}, 1, \frac{8}{3}, \frac{2}{3}, 5).

Sample Input 2

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

Sample Output 2

5 6

Sample Input 3

20 20
998769066 273215338 827984962 78974225 994243956 791478211 891861897 680427073 993663022 219733184 570206440 43712322 66791680 164318676 209536492 137458233 289158777 461179891 612373851 330908158
12 18 769877494
9 13 689822685
6 13 180913148
2 16 525285434
2 14 98115570
14 17 622616620
8 12 476462455
13 17 872412050
14 15 564176146
7 13 143650548
2 5 180435257
4 10 82903366
1 2 643996562
8 10 262860196
10 14 624081934
11 13 581257775
9 19 381806138
3 12 427930466
6 19 18249485
14 19 682428942

Sample Output 3

821382814 987210378 819486592 142238362 447960587 678128197 687469071 405316549 318941070 457450677 426617745 712263899 939619994 228431878 307695685 196179692 241456697 12668393 685902422 330908158