Problem Statement

You are given an N-by-N matrix A=(a_{i,j}), where a_{i,j} \in \{0,1\}.

We have the following directed graph.

• The graph has NK vertices numbered 1,2,\ldots,NK.
• The edges correspond to the NK-by-NK matrix X=(x_{i,j}) obtained by arranging K^2 copies of A in K rows and K columns (see Sample Input/Output 1 for an example). If x_{i,j}=1, there is a directed edge from vertex i to vertex j; if x_{i,j}=0, that edge does not exist.

Answer the following question for i=1,2,\ldots,Q.

• Find the shortest length (number of edges) of a path from vertex s_i to vertex t_i. If there is no such path, print -1 instead.

Constraints

• 1 \leq N \leq 100
• 1 \leq K \leq 10^9
• a_{i,j} \in \{0,1\}
• 1 \leq Q \leq 100
• 1 \leq s_i,t_i \leq NK
• s_i \neq t_i
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

1
1
1
3

Below is the matrix X representing the edges.

1 1 1 1 1 1
1 1 0 1 1 0
0 1 0 0 1 0
1 1 1 1 1 1
1 1 0 1 1 0
0 1 0 0 1 0

Sample Input 2

4 1000000000
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
1
1 4000000000

Sample Output 2

-1

There is no edge.

Problem Statement

We have variables a and b. Initially, a=A and b=B.

Takahashi will repeat the following operation while both a and b are greater than or equal to 1.

• Let g be the greatest common divisor of a and b, and replace a and b with a-g and b-g, respectively.

How many times will he perform the operation?

Constraints

• 1 \leq A,B \leq 10^{12}
• A and B are integers.

Sample Input 1

15 9

Sample Output 1

2

We start with a=15,b=9 and perform the following.

• Let g=3, and replace a and b with 12(=15-3) and 6(=9-3), respectively.
• Let g=6, and replace a and b with 6(=12-6) and 0(=6-6), respectively. b is no longer greater than or equal to 1, so the iteration terminates.

Sample Input 2

1 1

Sample Output 2

1

Sample Input 3

12345678910 10987654321

Sample Output 3

36135

Problem Statement

You are given a sequence of positive integers: A=(a_1,\ldots,a_N).

Determine whether it is possible to make all elements of A equal by repeating the following operation between 0 and 10^4 times, inclusive. If it is possible, show one way to do so.

• Choose a permutation (p_1,\ldots,p_N) of (1,\ldots,N), and replace A with (a_1+p_1,\ldots,a_N+p_N).

Constraints

• 2 \leq N \leq 50
• 1 \leq a_i \leq 50
• All values in the input are integers.

Sample Input 1

2
15 9

Sample Output 1

Yes
8
1 2
1 2
1 2
1 2
2 1
1 2
1 2
1 2

This sequence of 8 operations makes A = (24,24), where all elements are equal.

Sample Input 2

5
1 2 3 10 10

Sample Output 2

No

Sample Input 3

4
1 1 1 1

Sample Output 3

Yes
0

All elements of A are equal from the beginning.

Problem Statement

We have a sequence X, which is initially empty.
Takahashi has performed the following operation for i=1,2,\ldots,N in this order.

• Append l_i,l_i+1,\ldots,r_i in this order to the end of X.

Find the greatest length of a strictly increasing subsequence of the final X.

Constraints

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

Sample Input 1

4
1 1
2 4
10 11
7 10

Sample Output 1

8

The final X is (1,2,3,4,10,11,7,8,9,10).
The 1-st, 2-nd, 3-rd, 4-th, 7-th, 8-th, 9-th, and 10-th elements form a strictly increasing subsequence with the greatest length.

Sample Input 2

4
1 1
1 1
1 1
1 1

Sample Output 2

1

The final X is (1,1,1,1).

Sample Input 3

1
1 1000000000

Sample Output 3

1000000000

Problem Statement

You are given a positive integer N, and M pairs of positive integers: (a_0,b_0),\ldots,(a_{M-1},b_{M-1}) (note that a_i and b_i start with index 0).

We have the following sequence of non-negative integers X=(x_1,\ldots,x_N).

• x_i is determined as follows.
  1. Let l=1, r=N, and t=0.
  2. Let m=\left \lfloor \dfrac{a_{t \bmod M} \times l + b_{t \bmod M} \times r}{a_{t \bmod M} +b_{t \bmod M}} \right \rfloor (\lfloor x \rfloor is the greatest integer not exceeding x). If m=i, let x_i=t and terminate.
  3. If l \leq i \lt m, let r=m-1; otherwise, let l=m+1. Increment t by 1 and return to step 2.

Find \sum_{j=c_i}^{d_i-1} |x_j - x_{j+1}| for i=1,2,\ldots,Q.
It can be proved that the answers are at most 10^{18} under the constraints of this problem.

Constraints

• 2 \leq N \leq 10^{15}
• 1 \leq M \leq 100
• 1 \leq a_i,b_i \leq 1000
• \max \left (\dfrac{a_i}{b_i},\dfrac{b_i}{a_i}\right ) \leq 2
• 1 \leq Q \leq 10^4
• 1 \leq c_i \lt d_i \leq N
• All values in the input are integers.

Sample Input 1

5 1
1 1
3
1 2
2 4
3 5

Sample Output 1

1
3
2

We have X=(1,2,0,1,2). For example, x_1 is determined as follows.

• Let l=1, r=5(=N), and t=0.
• Let m=3(=\left \lfloor \dfrac{1 \times 1 + 1 \times 5}{1+1} \right \rfloor).
• Since l \leq 1 \lt m, let r=2(=m-1). Increment t by 1 to 1.
• Let m=1(= \left \lfloor \dfrac{1 \times 1 + 1 \times 2}{1+1} \right \rfloor ). Since m=1, let x_1=1(=t) and terminate.

The answer to the question for (c_1,d_1), for example, is \sum_{j=c_i}^{d_i-1} |x_j - x_{j+1}| = |x_1-x_2| = 1.

Sample Input 2

1000000000000000 2
15 9
9 15
3
100 10000
5000 385723875
150 17095708

Sample Output 2

19792
771437738
34191100

Problem Statement

A sequence X is called good when the following holds.

• X can be emptied by repeating the following operation zero or more times.
  • Delete two adjacent elements x_i and x_{i+1} of X such that x_i \neq x_{i+1}.

You are given a sequence with 2N elements: A=(a_1,\ldots,a_{2N}).
Among the 2^{2N-1} ways to divide A into one or more contiguous subsequences, how many are such that all those contiguous subsequences are good? Find the count modulo 998244353.

Constraints

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

Sample Input 1

3
1 1 2 3 4 5

Sample Output 1

2

The following two divisions satisfy the condition.

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

Sample Input 2

1
1 2

Sample Output 2

1

Sample Input 3

1
1 1

Sample Output 3

0

Sample Input 4

12
4 2 17 12 18 15 17 4 22 6 9 20 21 16 23 16 13 2 20 15 16 3 7 15

Sample Output 4

2048