Problem Statement

There are N seats in a row, numbered 1, 2, \ldots, N.

The state of the seats is given by a string S of length N consisting of # and .. If the i-th character of S is #, it means seat i is occupied; if it is ., seat i is unoccupied.

Find the number of integers i between 1 and N - 2, inclusive, that satisfy the following condition:

• Seats i and i + 2 are occupied, and seat i + 1 is unoccupied.

Constraints

• N is an integer satisfying 1 \leq N \leq 2 \times 10^5.
• S is a string of length N consisting of # and ..

Sample Input 1

6
#.##.#

Sample Output 1

2

i = 1 and 4 satisfy the condition, so the answer is 2.

Sample Input 2

1
#

Sample Output 2

0

Sample Input 3

9
##.#.#.##

Sample Output 3

3

Problem Statement

Given a string S, print AC if it perfectly matches Hello,World!; otherwise, print WA.

Constraints

• 1 \le |S| \le 15
• S consists of English lowercase letters, English uppercase letters, ,, and !.

Sample Input 1

Hello,World!

Sample Output 1

AC

The string S perfectly matches Hello,World!.

Sample Input 2

Hello,world!

Sample Output 2

WA

The seventh character from the beginning should be an uppercase W in Hello,World!, but S has a lowercase w in that position. Thus, S does not match Hello,World!.

Sample Input 3

Hello!World!

Sample Output 3

WA

Problem Statement

You are given two strings S and T consisting of lowercase English letters.

Determine if there exists a pair of integers c and w such that 1 \leq c \leq w < |S| and the following condition is satisfied. Here, |S| denotes the length of the string S. Note that w must be less than |S|.

• If S is split at every w characters from the beginning, the concatenation of the c-th characters of the substrings of length at least c in order equals T.

Constraints

• S and T are strings consisting of lowercase English letters.
• 1 \leq |T| \leq |S| \leq 100

Sample Input 1

atcoder toe

Sample Output 1

Yes

If S is split at every two characters, it looks like this:

at
co
de
r

Then, the concatenation of the 2nd characters of the substrings of length at least 2 is toe, which equals T. Thus, print Yes.

Sample Input 2

beginner r

Sample Output 2

No

w=|S| is not allowed, and no pair of integers 1 \leq c \leq w < |S| satisfies the condition. Thus, print No.

Sample Input 3

verticalreading agh

Sample Output 3

No

Problem Statement

There are N cities numbered 1, \dots, N, and M roads connecting cities.
The i-th road (1 \leq i \leq M) connects city A_i and city B_i.

Print N lines as follows.

• Let d_i be the number of cities directly connected to city i \, (1 \leq i \leq N), and those cities be city a_{i, 1}, \dots, city a_{i, d_i}, in ascending order.
• The i-th line (1 \leq i \leq N) should contain d_i + 1 integers d_i, a_{i, 1}, \dots, a_{i, d_i} in this order, separated by spaces.

Constraints

• 2 \leq N \leq 10^5
• 1 \leq M \leq 10^5
• 1 \leq A_i \lt B_i \leq N \, (1 \leq i \leq M)
• (A_i, B_i) \neq (A_j, B_j) if (i \neq j).
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

3 2 3 6
2 1 5
2 1 6
0
2 2 6
3 1 3 5

The cities directly connected to city 1 are city 2, city 3, and city 6. Thus, we have d_1 = 3, a_{1, 1} = 2, a_{1, 2} = 3, a_{1, 3} = 6, so you should print 3, 2, 3, 6 in the first line in this order, separated by spaces.

Note that a_{i, 1}, \dots, a_{i, d_i} must be in ascending order. For instance, it is unacceptable to print 3, 3, 2, 6 in the first line in this order.

Sample Input 2

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

Sample Output 2

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

Problem Statement

You have N socks. The color of the i-th sock is A_i.

You want to perform the following operation as many times as possible. How many times can it be performed at most?

• Choose two same-colored socks that are not paired yet, and pair them.

Constraints

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

Sample Input 1

6
4 1 7 4 1 4

Sample Output 1

2

You can do the operation twice as follows.

• Choose two socks with the color 1 and pair them.
• Choose two socks with the color 4 and pair them.

Then, you will be left with one sock with the color 4 and another with the color 7, so you can no longer do the operation. There is no way to do the operation three or more times, so you should print 2.

Sample Input 2

1
158260522

Sample Output 2

0

Sample Input 3

10
295 2 29 295 29 2 29 295 2 29

Sample Output 3

4

Problem Statement

A positive integer x is called a 321-like Number when it satisfies the following condition. This definition is the same as the one in Problem A.

• The digits of x are strictly decreasing from top to bottom.
• In other words, if x has d digits, it satisfies the following for every integer i such that 1 \le i < d:
  • (the i-th digit from the top of x) > (the (i+1)-th digit from the top of x).

Note that all one-digit positive integers are 321-like Numbers.

For example, 321, 96410, and 1 are 321-like Numbers, but 123, 2109, and 86411 are not.

Find the K-th smallest 321-like Number.

Constraints

• All input values are integers.
• 1 \le K
• At least K 321-like Numbers exist.

Sample Input 1

15

Sample Output 1

32

The 321-like Numbers are (1,2,3,4,5,6,7,8,9,10,20,21,30,31,32,40,\dots) from smallest to largest.
The 15-th smallest of them is 32.

Sample Input 2

321

Sample Output 2

9610

Sample Input 3

777

Sample Output 3

983210

Problem Statement

You are given a simple undirected graph with N vertices and M edges. The vertices are numbered from 1 through N, and the edges are numbered from 1 through M. Edge i connects Vertex U_i and Vertex V_i.

You are given integers K, S, T, and X. How many sequences A = (A_0, A_1, \dots, A_K) are there satisfying the following conditions?

• A_i is an integer between 1 and N (inclusive).
• A_0 = S
• A_K = T
• There is an edge that directly connects Vertex A_i and Vertex A_{i+1}.
• Integer X\ (X≠S,X≠T) appears even number of times (possibly zero) in sequence A.

Since the answer can be very large, find the answer modulo 998244353.

Constraints

• All values in input are integers.
• 2≤N≤2000
• 1≤M≤2000
• 1≤K≤2000
• 1≤S,T,X≤N
• X≠S
• X≠T
• 1≤U_i<V_i≤N
• If i ≠ j, then (U_i, V_i) ≠ (U_j, V_j).

Sample Input 1

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

Sample Output 1

4

The following 4 sequences satisfy the conditions:

• (1, 2, 1, 2, 3)
• (1, 2, 3, 2, 3)
• (1, 4, 1, 4, 3)
• (1, 4, 3, 4, 3)

On the other hand, (1, 2, 3, 4, 3) and (1, 4, 1, 2, 3) do not, since there are odd number of occurrences of 2.

Sample Input 2

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

Sample Output 2

0

The graph is not necessarily connected.

Sample Input 3

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

Sample Output 3

952504739

Find the answer modulo 998244353.

Problem Statement

You are given positive integers N, K, and an integer sequence of length N: A = (A_1, A_2, \dots, A_N).

Find \displaystyle \sum_{1\leq l\leq r\leq N} \Bigg(\sum_{l\leq i\leq r} A_i\Bigg)^K, modulo 998244353.

Constraints

• 1\leq N \leq 2\times 10^5
• 1\leq K \leq 10
• 0 \leq A_i < 998244353
• All input values are integers.

Sample Input 1

3 2
3 1 2

Sample Output 1

75

The value is A_1^2+A_2^2+A_3^2+(A_1+A_2)^2+(A_2+A_3)^2+(A_1+A_2+A_3)^2=3^2+1^2+2^2+4^2+3^2+6^2=75.

Sample Input 2

1 10
0

Sample Output 2

0

Sample Input 3

10 5
91 59 85 60 57 72 12 3 27 16

Sample Output 3

428633385

Be sure to find the sum modulo 998244353.