Problem Statement

How many triples A,B,C of integers between L and R (inclusive) satisfy A-B=C?

You will be given T cases. Solve each of them.

Constraints

• 1 \leq T \leq 2\times 10^4
• 0\le L \le R \le 10^6
• All values in input are integers.

Sample Input 1

5
2 6
0 0
1000000 1000000
12345 67890
0 1000000

Sample Output 1

6
1
0
933184801
500001500001

In the first case, we have the following six triples:

• 4 - 2 = 2
• 5 - 2 = 3
• 5 - 3 = 2
• 6 - 2 = 4
• 6 - 3 = 3
• 6 - 4 = 2

Problem Statement

Snuke has come to Seisu-ya (integer shop) with an integer B in his hand. In Seiyu-ya, you can exchange your integer for another integer by paying money.

More specifically, you can use the following two services any number of times in any order:

• Pay 1 yen (the currency of Japan) to multiply your integer by -1.
• Pay 2 yen to subtract 1 from your integer.

How many integers are there that Snuke can get for at most C yen?

Constraints

• -10^{18}\le B \le 10^{18}
• 1\le C \le 10^{18}
• All values in input are integers.

Sample Input 1

11 2

Sample Output 1

3

There are three numbers that Snuke can get: -11, 10, and 11, as follows:

• by doing nothing, he can get 11 for 0 yen;
• by multiplying 11 by -1, he can get -11 for 1 yen;
• by subtracting 1 from 11, he can get 10 for 2 yen.

Sample Input 2

0 4

Sample Output 2

4

There are four numbers that Snuke can get: -2, -1, 0, and 1, as follows:

• by doing nothing, he can get 0 for 0 yen;
• by subtracting 1 from 0, he can get -1 for 2 yen;
• by subtracting 1 from 0 and then multiplying by -1, he can get 1 for 3 yen;
• by subtracting 1 from 0 and then subtracting 1 again, he can get -2 for 4 yen.

Sample Input 3

112 20210213

Sample Output 3

20210436

Sample Input 4

-211 1000000000000000000

Sample Output 4

1000000000000000422

Problem Statement

Takahashi and Aoki will play a game using a rooted tree with n vertices, numbered 1 through n. The root of the tree is Vertex 1. For each v=2,\dots,n, the parent of Vertex v is p_v. Initially, there is one coin on each vertex. Additionally, there is a piece on Vertex 1.

Takahashi and Aoki will alternately do the following operation, with Takahashi going first:

• If there is a coin on the vertex occupied by the piece: get the coin and end his turn.
• If there is no coin on the vertex occupied by the piece: move the piece (or end the game) as follows.
  • If there are vertices with coins on them among the children of the vertex occupied by the piece, choose one such vertex, move the piece to that vertex, and end his turn.
  • Otherwise, if the piece is on the root, end the game; if not, move the piece to the parent of the vertex occupied by the piece and end his turn.

Both Takahashi and Aoki will play optimally to maximize the number of coins they will get. Find the number of coins Takahashi will get.

Constraints

• 2\le n \le 10^5
• 1\le p_v \lt v

Sample Input 1

10
1 2 3 4 5 6 7 8 9

Sample Output 1

10

There is no choice for the players, and the game will always go as follows, so Takahashi will get every coin.

• Takahashi gets the coin on Vertex 1.
• Aoki moves the piece to Vertex 2.
• Takahashi gets the coin on Vertex 2.
• Aoki moves the piece to Vertex 3.
• \vdots
• Takahashi gets the coin on Vertex 10.
• Aoki moves the piece to Vertex 9.
• Takahashi moves the piece to Vertex 8.
• Aoki moves the piece to Vertex 7.
• \vdots
• Takahashi moves the piece to Vertex 2.
• Aoki moves the piece to Vertex 1.
• The game ends.

Sample Input 2

5
1 2 3 1

Sample Output 2

2

First, Takahashi gets the coin on Vertex 1. Then, Aoki can move the piece to Vertex 2 or Vertex 5. If he moves it to Vertex 2, Aoki will eventually get just the coin on Vertex 5. On the other hand, if he moves it to Vertex 5, Aoki will eventually get the coins on Vertex 2, 3, and 4. Since Aoki will play optimally to maximize the number of coins he will get, he will choose to move the piece to Vertex 5. Thus, Takahashi will get two coins.

Sample Input 3

10
1 1 3 1 3 6 7 6 6

Sample Output 3

5

Problem Statement

Takahashi is on a skating rink consisting of H rows and W columns of squares. Let (r, c) denote the square at the r-th row from the north and c-th column from the west. Each square is ice or ground; (r, c) is ground if S_{r, c} is # and ice if S_{r, c} is .. There are walls around the rink.

When Takahashi is standing still on the rink, he can start moving to the east, west, south, or north. After he starts moving, he will keep moving in the same direction, until he bumps into a wall or he is on a ground square (other than the square where he started moving).

We say the rink is efficient for (r, c) when the following condition is satisfied:

• There is a sequence of moves that starts at (r, c), standing still, and passes every square. (It is not required to stop on each square.)

Takahashi wants to change some number of ice squares to ground squares so that the rink is efficient for every square. How many squares does he need to change, at least?

Constraints

• 2\le H,W \le 1000
• S_{r,c} is # or ..

Sample Input 1

3 9
.........
.........
.........

Sample Output 1

1

Initially, it is impossible to start at (1, 1) and pass (2, 2). One way to meet the objective is to change the rink as follows:

.........
........#
.........

Sample Input 2

10 10
..........
#...#.....
..........
..........
..........
....#.....
.#......#.
..........
..........
..........

Sample Output 2

6

Problem Statement

We applied the following operation m times on the sequence (1,2,\dots,n), and it resulted in (a_1,\dots ,a_n).

• Erase one element. Then, add the erased element to the beginning or end of the sequence.

Find the number of possible sequences of the m operations, modulo 998244353.

Here, two sequences of operations are considered the same when, in every operation, the same element is chosen and added to the same position.

Constraints

• 2\le n \le 3000
• 1\le m \le 3000
• a_1,\dots ,a_n is a permutation of 1,\dots,n.

Sample Input 1

5 2
1 2 4 5 3

Sample Output 1

5

There are five possible sequences of operations, as follows:

• Erase 1 and add it to the beginning, which results in (1,2,3,4,5). Then, erase 3 and add it to the end, which results in (1,2,4,5,3).
• Erase 3 and add it to the beginning, which results in (3,1,2,4,5). Then, erase 3 and add it to the end, which results in (1,2,4,5,3).
• Erase 3 and add it to the end, which results in (1,2,4,5,3). Then, erase 1 and add it to the beginning, which results in (1,2,4,5,3).
• Erase 3 and add it to the end, which results in (1,2,4,5,3). Then, erase 3 and add it to the end, which results in (1,2,4,5,3).
• Erase 5 and add it to the end, which results in (1,2,3,4,5). Then, erase 3 and add it to the end, which results in (1,2,4,5,3).

Sample Input 2

2 16
1 2

Sample Output 2

150994942

Two of the four kinds of operations have no effect on the sequence, and the other two swap the two elements. From this fact, we can show that there are 4^m/2 = 2^{31} = 2147483648 sequences of operations - half of all possible sequences - that we want to count. Thus, the answer is 2147483648 modulo 998244353, that is, 150994942.

Sample Input 3

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

Sample Output 3

129989699

Problem Statement

Snuke is playing a game using n kinds of cards called Card 1 through Card n. There are m kinds of card packs available in this game; the i-th pack contains s_{i,j} copies of Card j. Every pack contains at least one card.

Initially, Snuke has c_j copies of Card j (it is guaranteed that he has at least one card in total).

He can do the following operations any number of times in any order:

• Get a card pack: Choose i=1, \dots, or m and get all cards contained in the i-th pack.
• Exchange cards: Choose j=1, \dots, or n, discard 2j copies of Card j, and get one copy of Card ((j \text{ mod } n) + 1). (He must have at least 2j copies of Card j.)

Snuke wants to have as few cards as possible in total. Find the minimum number of cards that Snuke can end up with.

Constraints

• 2 \le n \le 16
• 1 \le m \le 50
• 0 \le s_{i,j}, c_j \lt 2j
• c_1+\dots +c_n>0
• s_{i,1}+\dots +s_{i,n}>0

Sample Input 1

3 1
0 3 5
0 1 0

Sample Output 1

1

Let (a_1, a_2, a_3) denote the fact that Snuke has a_1 copies of Card 1, a_2 copies of Card 2, and a_3 copies of Card 3. The following sequence of operations leaves Snuke with one card:

• get the 1-st card pack, which results in (0,4,5);
• exchange cards with j=2, which results in (0,0,6);
• exchange cards with j=3, which results in (1,0,0).

It is impossible to end up with zero cards, so this is the minimum possible number.

Sample Input 2

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

Sample Output 2

2

By getting two packs of the second kind and one pack of the first kind, and then exchanging cards some number of times, Snuke can end up with one copy of Card 4 and one copy of Card 5.

Sample Input 3

12 10
0 2 4 4 1 5 6 8 0 9 18 19
1 2 4 3 4 0 6 10 9 18 5 7
0 3 0 1 1 4 11 13 9 19 9 10
1 2 4 1 5 8 1 6 15 0 11 1
0 2 0 6 9 3 13 14 16 9 14 14
1 3 2 5 6 1 9 7 1 7 6 22
0 0 4 5 2 3 8 3 13 14 17 4
0 3 3 4 0 7 0 9 14 2 17 14
0 2 4 1 3 3 3 14 17 6 15 13
0 0 1 0 1 0 4 5 9 4 17 17
1 2 1 3 5 7 0 13 7 6 1 0

Sample Output 3

9