Problem Statement

Streamer Takahashi has decided to stream from L o'clock to R o'clock (using the 24-hour clock).

He has N listeners, and the i-th listener can watch the stream from X_i o'clock to Y_i o'clock.

How many listeners can watch Takahashi's stream from beginning to end?

Constraints

• 1\leq N\leq 100
• 0\leq L\lt R\leq 23
• 0\leq X_i\lt Y_i\leq 23
• All input values are integers.

Sample Input 1

5 19 22
17 23
20 23
19 22
0 23
12 20

Sample Output 1

3

The listeners who can watch Takahashi's stream from beginning to end are the 1st, 3rd, and 4th listeners.

Sample Input 2

3 12 13
0 1
0 1
0 1

Sample Output 2

0

No listeners can watch Takahashi's stream from beginning to end.

Sample Input 3

10 8 14
5 20
14 21
9 21
5 23
8 10
0 14
3 8
2 6
0 16
5 20

Sample Output 3

5

Problem Statement

You are given positive integers N, L, and R.
For a sequence A = (1, 2, \dots, N) of length N, an operation of reversing the L-th through R-th elements was performed once.
Print the sequence after this operation.

Constraints

• All input values are integers.
• 1 \leq L \leq R \leq N \leq 100

Sample Input 1

5 2 3

Sample Output 1

1 3 2 4 5

Initially, A = (1, 2, 3, 4, 5).
After reversing the second through third elements, the sequence becomes (1, 3, 2, 4, 5), which should be printed.

Sample Input 2

7 1 1

Sample Output 2

1 2 3 4 5 6 7

It is possible that L = R.

Sample Input 3

10 1 10

Sample Output 3

10 9 8 7 6 5 4 3 2 1

It is possible that L = 1 or R = N.

Problem Statement

You are given an N \times N grid S and an M \times M grid T. The cell at the i-th row from the top and the j-th column from the left is denoted by (i,j).

The colors of the cells in S and T are represented by N^2 characters S_{i,j} (1\leq i,j\leq N) and M^2 characters T_{i,j} (1\leq i,j\leq M), respectively. In grid S, cell (i,j) is white if S_{i,j} is ., and black if S_{i,j} is #. The same applies for grid T.

Find T within S. More precisely, output integers a and b (1 \leq a,b \leq N-M+1) that satisfy the following condition:

• S_{a+i-1,b+j-1} = T_{i,j} for every i,j (1\leq i,j \leq M).

Constraints

• 1 \leq M \leq N \leq 50
• N and M are integers.
• Each of S_{i,j} and T_{i,j} is . or #.
• There is exactly one pair (a,b) satisfying the condition.

Sample Input 1

3 2
#.#
..#
##.
.#
#.

Sample Output 1

2 2

The 2 \times 2 subgrid of S from the 2nd to the 3rd row and from the 2nd to the 3rd column matches T.

Sample Input 2

2 1
#.
##
.

Sample Output 2

1 2

Problem Statement

In the calendar of AtCoderLand, a year consists of M months: month 1, month 2, \dots, month M. The i-th month consists of D_i days: day 1, day 2, \dots, day D_i.
Furthermore, the number of days in a year is odd, that is, D_1+D_2+\dots+D_M is odd.
Find what day of what month is the middle day of the year.
In other words, let day 1 of month 1 be the first day, and find a and b such that the ((D_1+D_2+\dots+D_M+1)/2)-th day is day b of month a.

Constraints

• All input values are integers.
• 1 \le M \le 100
• 1 \le D_i \le 100
• D_1 + D_2 + \dots + D_M is odd.

Sample Input 1

12
31 28 31 30 31 30 31 31 30 31 30 31

Sample Output 1

7 2

In this input, a year consists of 31+28+31+30+31+30+31+31+30+31+30+31=365 days.
Let us find the middle day, which is the ((365+1)/2 = 183)-th day.

• Months 1,2,3,4,5,6 contain a total of 181 days.
• Day 1 of month 7 is the 182-th day.
• Day 2 of month 7 is the 183-th day.

Thus, the answer is day 2 of month 7.

Sample Input 2

1
1

Sample Output 2

1 1

Sample Input 3

6
3 1 4 1 5 9

Sample Output 3

5 3

Problem Statement

There are N types of chemicals 1,2,\dots,N. Your goal is to create a state where all of them are mixed.
You are given a string S of length 2^N-1 consisting of 0 and 1, which represents the following information:

• First, define state i (1 \le i \le 2^N-1) where one or more types of chemicals are mixed as follows:
  • When the k-th digit (1 \le k \le N) from the bottom in the binary representation of i is 1, and only then, chemical k is included.
  • For example, 13 in binary is 1101_{(2)}, so state 13 represents a state where chemicals 1,3,4 are mixed.
• When the i-th character of S is 0, state i is safe.
• When the i-th character of S is 1, state i is dangerous.

You mix chemicals using the following operation:

• First, prepare an empty bottle.
• Next, repeat the following:
  • Choose one type of chemical that has not yet been poured into the bottle and pour it into the bottle.
  • At this time, the chemicals mixed in the bottle must not be in a dangerous state.

Determine whether this operation can create a state where all chemicals are mixed.

You are given T test cases; solve each of them.

Constraints

• T is an integer between 1 and 40000, inclusive.
• N is an integer between 1 and 18, inclusive.
• S is a string of length 2^N-1 consisting of 0 and 1.
• The sum of |S| = 2^N-1 in each input does not exceed 5 \times 10^5.

Sample Input 1

5
3
0010000
3
0010110
1
1
2
100
4
001110010101110

Sample Output 1

Yes
No
No
Yes
Yes

This input contains five test cases.

The 1st case is as follows:

• There are three types of chemicals.
• Only state 3 where chemicals 1,2 are mixed is dangerous, and the other states are safe.
• For example, you can create a state where all chemicals are mixed with the following procedure:
  • First, pour chemical 2 into the bottle. Only chemical 2 is mixed in the bottle, which is state 2, so it is safe.
  • Next, pour chemical 3 into the bottle. Chemicals 2,3 are mixed in the bottle, which is state 6, so it is safe.
  • Finally, pour chemical 1 into the bottle. Chemicals 1,2,3 are mixed in the bottle, which is state 7, so it is safe.

The 2nd case is as follows:

• There are three types of chemicals.
• State 3 where chemicals 1,2 are mixed, state 5 where chemicals 1,3 are mixed, and state 6 where chemicals 2,3 are mixed are dangerous, and the other states are safe.
• For this case, it is impossible to create a state where all chemicals are mixed.

The 3rd case is as follows:

• There is one type of chemical.
• Since state 1 where only chemical 1 is mixed is dangerous, it is impossible to create a state where all chemicals are mixed.

Problem Statement

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

Process Q queries in order. There are two types of queries, given in the following formats:

• 1 c: Perform the operation of moving the first element of A to the end c times.
• 2 l r: Output the value of \displaystyle \sum_{i=l}^r A_i.

Constraints

• 1\le N\le 2\times 10^5
• 1\le Q\le 2\times 10^5
• 1\le A_i \le 10^9
• 1\le c\le N
• 1\le l\le r \le N
• At least one query of the second type exists.
• All input values are integers.

Sample Input 1

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

Sample Output 1

8
9

Each query is processed as follows:

• First query: A_1+A_2+A_3=3+1+4=8, so output 8.
• Second query: A=(3,1,4,5) changes to A=(1,4,5,3).
• Third query: A_2+A_3=4+5=9, so output 9.

Sample Input 2

5 7
1 2 4 8 16
2 1 5
1 4
1 5
2 1 5
2 2 4
1 1
2 3 3

Sample Output 2

31
31
7
4

Problem Statement

You are given a string S of length N consisting of digits.

Find the number of square numbers that can be obtained by interpreting a permutation of S as a decimal integer.

More formally, solve the following.

Let s _ i be the number corresponding to the i-th digit (1\leq i\leq N) from the beginning of S.

Find the number of square numbers that can be represented as \displaystyle \sum _ {i=1} ^ N s _ {p _ i}10 ^ {N-i} with a permutation P=(p _ 1,p _ 2,\ldots,p _ N) of (1, \dots, N).

Constraints

• 1\leq N\leq 13
• S is a string of length N consisting of digits.
• N is an integer.

Sample Input 1

4
4320

Sample Output 1

2

For P=(4,2,3,1), we have s _ 4\times10 ^ 3+s _ 2\times10 ^ 2+s _ 3\times10 ^ 1+s _ 1=324=18 ^ 2.
For P=(3,2,4,1), we have s _ 3\times10 ^ 3+s _ 2\times10 ^ 2+s _ 4\times10 ^ 1+s _ 1=2304=48 ^ 2.

No other permutations result in square numbers, so you should print 2.

Sample Input 2

3
010

Sample Output 2

2

For P=(1,3,2) or P=(3,1,2), we have \displaystyle\sum _ {i=1} ^ Ns _ {p _ i}10 ^ {N-i}=1=1 ^ 2.
For P=(2,1,3) or P=(2,3,1), we have \displaystyle\sum _ {i=1} ^ Ns _ {p _ i}10 ^ {N-i}=100=10 ^ 2.

No other permutations result in square numbers, so you should print 2. Note that different permutations are not distinguished if they result in the same number.

Sample Input 3

13
8694027811503

Sample Output 3

840

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

There are N towns numbered Town 1, Town 2, \ldots, Town N.
There are also M Teleporters, each of which connects two towns bidirectionally so that a person can travel from one to the other in one minute.

The i-th Teleporter connects Town U_i and Town V_i bidirectionally. However, for some of the Teleporters, one of the towns it connects is undetermined; U_i=0 means that one of the towns the i-th Teleporter connects is Town V_i, but the other end is undetermined.

For i=1,2,\ldots,N, answer the following question.

When the Teleporters with undetermined ends are all determined to be connected to Town i, how many minutes is required at minimum to travel from Town 1 to Town N? If it is impossible to travel from Towns 1 to N using Teleporters only, print -1 instead.

Constraints

• 2 \leq N \leq 3\times 10^5
• 1\leq M\leq 3\times 10^5
• 0\leq U_i<V_i\leq N
• If i \neq j, then (U_i,V_i)\neq (U_j,V_j).
• All values in input are integers.

Sample Input 1

3 2
0 2
1 2

Sample Output 1

-1 -1 2

When the Teleporters with an undetermined end are all determined to be connected to Town 1,
the 1-st and the 2-nd Teleporters both connect Towns 1 and 2. Then, it is impossible to travel from Town 1 to Town 3.

When the Teleporters with an undetermined end are all determined to be connected to Town 2,
the 1-st Teleporter connects Town 2 and itself, and the 2-nd one connects Towns 1 and 2. Again, it is impossible to travel from Town 1 to Town 3.

When the Teleporters with an undetermined end are all determined to be connected to Town 3,
the 1-st Teleporter connects Town 3 and Town 2, and the 2-nd one connects Towns 1 and 2. In this case, we can travel from Town 1 to Town 3 in two minutes.

• Use the 2-nd Teleporter to travel from Town 1 to Town 2.
• Use the 1-st Teleporter to travel from Town 2 to Town 3.

Therefore, -1,-1, and 2 should be printed in this order.

Note that, depending on which town the Teleporters with an undetermined end are connected to, there may be a Teleporter that connects a town and itself, or multiple Teleporters that connect the same pair of towns.

Sample Input 2

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

Sample Output 2

3 3 3 3 2