Problem Statement

You are given an array A of length N. Your task is to divide it into several contiguous subarrays. Here, all subarrays obtained must be sorted in either non-decreasing or non-increasing order. At least how many subarrays do you need to divide A into?

Constraints

• 1 \leq N \leq 10^5
• 1 \leq A_i \leq 10^9
• Each A_i is an integer.

Sample Input 1

6
1 2 3 2 2 1

Sample Output 1

2

One optimal solution is to divide the array into [1,2,3] and [2,2,1].

Sample Input 2

9
1 2 1 2 1 2 1 2 1

Sample Output 2

5

Sample Input 3

7
1 2 3 2 1 999999999 1000000000

Sample Output 3

3

Problem Statement

You are given a connected undirected simple graph, which has N vertices and M edges. The vertices are numbered 1 through N, and the edges are numbered 1 through M. Edge i connects vertices A_i and B_i. Your task is to find a path that satisfies the following conditions:

• The path traverses two or more vertices.
• The path does not traverse the same vertex more than once.
• A vertex directly connected to at least one of the endpoints of the path, is always contained in the path.

It can be proved that such a path always exists. Also, if there are more than one solution, any of them will be accepted.

Constraints

• 2 \leq N \leq 10^5
• 1 \leq M \leq 10^5
• 1 \leq A_i < B_i \leq N
• The given graph is connected and simple (that is, for every pair of vertices, there is at most one edge that directly connects them).

Sample Input 1

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

Sample Output 1

4
2 3 1 4

There are two vertices directly connected to vertex 2: vertices 3 and 4. There are also two vertices directly connected to vertex 4: vertices 1 and 2. Hence, the path 2 → 3 → 1 → 4 satisfies the conditions.

Sample Input 2

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

Sample Output 2

7
1 2 3 4 5 6 7

Problem Statement

There is a circle with a circumference of L. Each point on the circumference has a coordinate value, which represents the arc length from a certain reference point clockwise to the point. On this circumference, there are N ants. These ants are numbered 1 through N in order of increasing coordinate, and ant i is at coordinate X_i.

The N ants have just started walking. For each ant i, you are given the initial direction W_i. Ant i is initially walking clockwise if W_i is 1; counterclockwise if W_i is 2. Every ant walks at a constant speed of 1 per second. Sometimes, two ants bump into each other. Each of these two ants will then turn around and start walking in the opposite direction.

For each ant, find its position after T seconds.

Constraints

• All input values are integers.
• 1 \leq N \leq 10^5
• 1 \leq L \leq 10^9
• 1 \leq T \leq 10^9
• 0 \leq X_1 < X_2 < ... < X_N \leq L - 1
• 1 \leq W_i \leq 2

Sample Input 1

3 8 3
0 1
3 2
6 1

Sample Output 1

1
3
0

1.5 seconds after the ants start walking, ant 1 and 2 bump into each other at coordinate 1.5. 1 second after that, ant 1 and 3 bump into each other at coordinate 0.5. 0.5 seconds after that, that is, 3 seconds after the ants start walking, ants 1, 2 and 3 are at coordinates 1, 3 and 0, respectively.

Sample Input 2

4 20 9
7 2
9 1
12 1
18 1

Sample Output 2

7
18
18
1

Problem Statement

Joisino has a lot of red and blue bricks and a large box. She will build a tower of these bricks in the following manner.

First, she will pick a total of N bricks and put them into the box. Here, there may be any number of bricks of each color in the box, as long as there are N bricks in total. Particularly, there may be zero red bricks or zero blue bricks. Then, she will repeat an operation M times, which consists of the following three steps:

• Take out an arbitrary brick from the box.
• Put one red brick and one blue brick into the box.
• Take out another arbitrary brick from the box.

After the M operations, Joisino will build a tower by stacking the 2 \times M bricks removed from the box, in the order they are taken out. She is interested in the following question: how many different sequences of colors of these 2 \times M bricks are possible? Write a program to find the answer. Since it can be extremely large, print the count modulo 10^9+7.

Constraints

• 1 \leq N \leq 3000
• 1 \leq M \leq 3000

Sample Input 1

2 3

Sample Output 1

56

A total of six bricks will be removed from the box. The only impossible sequences of colors of these bricks are the ones where the colors of the second, third, fourth and fifth bricks are all the same. Therefore, there are 2^6 - 2 \times 2 \times 2 = 56 possible sequences of colors.

Sample Input 2

1000 10

Sample Output 2

1048576

Sample Input 3

1000 3000

Sample Output 3

693347555

Problem Statement

Joisino has a bar of length N, which has M marks on it. The distance from the left end of the bar to the i-th mark is X_i.

She will place several squares on this bar. Here, the following conditions must be met:

• Only squares with integral length sides can be placed.
• Each square must be placed so that its bottom side touches the bar.
• The bar must be completely covered by squares. That is, no square may stick out of the bar, and no part of the bar may be left uncovered.
• The boundary line of two squares may not be directly above a mark.

Examples of arrangements that satisfy/violate the conditions

The beauty of an arrangement of squares is defined as the product of the areas of all the squares placed. Joisino is interested in the sum of the beauty over all possible arrangements that satisfy the conditions. Write a program to find it. Since it can be extremely large, print the sum modulo 10^9+7.

Constraints

• All input values are integers.
• 1 \leq N \leq 10^9
• 0 \leq M \leq 10^5
• 1 \leq X_1 < X_2 < ... < X_{M-1} < X_M \leq N-1

Sample Input 1

3 1
2

Sample Output 1

13

There are two possible arrangements:

• Place a square of side length 1 to the left, and place another square of side length 2 to the right
• Place a square of side length 3

The sum of the beauty of these arrangements is (1 \times 1 \times 2 \times 2) + (3 \times 3) = 13.

Sample Input 2

5 2
2 3

Sample Output 2

66

Sample Input 3

10 9
1 2 3 4 5 6 7 8 9

Sample Output 3

100

Sample Input 4

1000000000 0

Sample Output 4

693316425

Problem Statement

There are N cards. The two sides of each of these cards are distinguishable. The i-th of these cards has an integer A_i printed on the front side, and another integer B_i printed on the back side. We will call the deck of these cards X. There are also N+1 cards of another kind. The i-th of these cards has an integer C_i printed on the front side, and nothing is printed on the back side. We will call this another deck of cards Y.

You will play Q rounds of a game. Each of these rounds is played independently. In the i-th round, you are given a new card. The two sides of this card are distinguishable. It has an integer D_i printed on the front side, and another integer E_i printed on the back side. A new deck of cards Z is created by adding this card to X. Then, you are asked to form N+1 pairs of cards, each consisting of one card from Z and one card from Y. Each card must belong to exactly one of the pairs. Additionally, for each card from Z, you need to specify which side to use. For each pair, the following condition must be met:

• (The integer printed on the used side of the card from Z) \leq (The integer printed on the card from Y)

If it is not possible to satisfy this condition regardless of how the pairs are formed and which sides are used, the score for the round will be -1. Otherwise, the score for the round will be the count of the cards from Z whose front side is used.

Find the maximum possible score for each round.

Constraints

• All input values are integers.
• 1 \leq N \leq 10^5
• 1 \leq Q \leq 10^5
• 1 \leq A_i ,B_i ,C_i ,D_i ,E_i \leq 10^9

Sample Input 1

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

Sample Output 1

0
1
2

For example, in the third round, the cards in Z are (4,1),(5,3),(3,1),(2,3). The score of 2 can be obtained by using front, back, back and front sides of them, and pair them with the fourth, third, first and second cards in Y, respectively. It is not possible to obtain a score of 3 or greater, and thus the answer is 2.

Sample Input 2

5
7 1
9 7
13 13
11 8
12 9
16 7 8 6 9 11
7
6 11
7 10
9 3
12 9
18 16
8 9
10 15

Sample Output 2

4
3
3
1
-1
3
2

Sample Input 3

9
89 67
37 14
6 1
42 25
61 22
23 1
63 60
93 62
14 2
67 96 26 17 1 62 56 92 13 38
11
93 97
17 93
61 57
88 62
98 29
49 1
5 1
1 77
34 1
63 27
22 66

Sample Output 3

7
9
8
7
7
9
9
10
9
7
9