Problem Statement

President K is designing a pattern represented by a grid with N rows and N columns. To achieve this, he has decided to paint each cell with a color represented by an integer number. Let us refer to the cell in the i-th row (1 \leq i \leq N) and j-th column (1 \leq j \leq N) as cell (i,j).

Currently, the cells in the first column and first row are already painted. Specifically, cell (i,1) (1 \leq i \leq N) is painted with color A_i and cell (1,j) (1 \leq j \leq N) is painted with color B_j. Note that A_1 = B_1.

For the remaining unpainted cells, President K is going to paint them by the following procedure:

• For each i=2,3,\dots,N in order, paint the cells in the i-th row as follows:
  • For each j=2,3,\dots,N in order, paint cell (i,j) with the color that has the larger number between:
    • The color of cell (i-1,j), and
    • The color of cell (i,j-1).
    If both colors have the same number, paint the cell with that color.

President K would like to determine the color that is painted on the largest number of cells after all N^2 cells have been painted, as well as the number of cells painted with that color.

Write a program that, given the size of the grid and the color information for the first column and first row, determines the color number painted on the largest number of cells and the number of cells painted with that color. If multiple colors are painted on the largest number of cells, output the largest color number among them.

Constraints

• 2 \leq N \leq 200\,000.
• 1 \leq A_i \leq 10^9 (1 \leq i \leq N).
• 1 \leq B_j \leq 10^9 (1 \leq j \leq N).
• A_1 = B_1.
• Given values are all integers.

Subtasks

1. (15 points) N \leq 500, A_i \leq 100\,000 (1 \leq i \leq N), B_j \leq 100\,000 (1 \leq j \leq N).
2. (10 points) N \leq 500.
3. (20 points) A_i \leq 2 (1 \leq i \leq N), B_j \leq 2 (1 \leq j \leq N).
4. (25 points) A_i < A_{i+1} (1 \leq i \leq N-1), B_j < B_{j+1} (1 \leq j \leq N-1).
5. (30 points) No additional constraints.

Sample Input 1

3
5 2 5
5 3 1

Sample Output 1

5 4

In this sample, the color of each cell in the grid will be as follows:

The color number painted on the largest number of cells is 5, which appears on 4 cells. Thus, print 5 and 4 in this order, separated by a space.

This sample input satisfies the constraints of Subtasks 1, 2, and 5.

Sample Input 2

3
1 7 8
1 3 5

Sample Output 2

8 3

In this sample, the color of each cell in the grid will be as follows:

The color numbers painted on the largest number of cells are 7 and 8, each painted on 3 cells. In this case, output the larger color number, 8, followed by the number of cells, 3, separated by a space.

This sample input satisfies the constraints of Subtasks 1, 2, 4, and 5.

Sample Input 3

4
2 1 2 1
2 1 1 2

Sample Output 3

2 10

This sample input satisfies the constraints of Subtasks 1, 2, 3, and 5.

Problem Statement

Bitaro, the brave hero, has set out on an adventure to defeat monsters.

Bitaro has a strength value, denoted as x, which starts at an initial value. There are N monsters, each labeled with a number from 1 to N. To defeat the i-th monster (1 \leq i \leq N), Bitaro must have a strength of at least A_i. Defeating the i-th monster increases Bitaro's strength by B_i.

Bitaro wants to defeat all the monsters using the following strategy:

1. Start with a specific monster j (1 \leq j \leq N) and defeat the monsters in order: j, j + 1, \ldots, N.
2. If j \geq 2, go back and defeat the monsters 1, 2, \ldots, j-1 in sequence.

Given the information about the monsters, write a program to determine the minimum initial strength x required for Bitaro to defeat all the monsters.

Constraints

• 2 \leq N \leq 500\,000.
• 0 \leq A_i \leq 10^9 (1 \leq i \leq N).
• 0 \leq B_i \leq 10^9 (1 \leq i \leq N).
• Given values are all integers.

Subtasks

1. (10 points) N \leq 2\,000, and the minimum initial strength x is 10 or less.
2. (21 points) N \leq 2\,000.
3. (19 points) The minimum initial strength x is 10 or less.
4. (22 points) B_i = 1 (1 \leq i \leq N).
5. (28 points) No additional constraints.

Sample Input 1

5
1 3 2 8 6
4 3 1 1 2

Sample Output 1

1

• Start with an initial strength of 1.
• Defeat monsters in the following order:
  1. Defeat monster 1. Strength increases by 4 to 5.
  2. Defeat monster 2. Strength increases by 3 to 8.
  3. Defeat monster 3. Strength increases by 1 to 9.
  4. Defeat monster 4. Strength increases by 1 to 10.
  5. Defeat monster 5. Strength increases by 2 to 12.

This sample input satisfies the constraints of Subtasks 1,2,3 and 5.

Sample Input 2

5
1 6 3 3 2
1 2 1 0 1

Sample Output 2

3

• Start with an initial strength of 3.
• Defeat monsters in the following order:
  1. Defeat monster 3. Strength increases by 1 to 4.
  2. Defeat monster 4. Strength increases by 0 to 4.
  3. Defeat monster 5. Strength increases by 1 to 5.
  4. Defeat monster 1. Strength increases by 1 to 6.
  5. Defeat monster 2. Strength increases by 2 to 8.

This sample input satisfies the constraints of Subtasks 1,2,3 and 5.

Sample Input 3

10
11 9 8 12 7 7 8 12 9 10
1 1 1 1 1 1 1 1 1 1

Sample Output 3

9

This sample input satisfies the constraints of all the subtasks.

Sample Input 4

7
1125 638 0 37 737 820 1202
23 984 558 350 52 345 580

Sample Output 4

0

This sample input satisfies the constraints of Subtasks 1,2,3 and 5.

Problem Statement

La Paz, the capital city of Bolivia, is famous as a tourist spot and for an aerial cable car called Mi Teleférico. You are now visiting La Paz for sightseeing, and you want to visit as many sightseeing places as possible. In this task, we consider the following simplified situation.

There are N aerial cable car stations in La Paz, numbered from 1 to N in ascending order of altitude. There are M one-way lines, numbered from 1 to M. There are P aerial cable car companies, numbered from 1 to P. Each line is managed by a single company. Line i (1 \leq i \leq M) is operated from station A_i to station B_i, and is managed by the company C_i. Here, the line always runs from the lower altitude station to the higher altitude station. In other words, A_i < B_i holds.

The Bureau of transportation of La Paz issued unlimited ride passes for convenience. Each ride pass contains 2 integers l, r, which satisfy 1 \leq l \leq r \leq P. The pass enables the possessor to ride lines, which are managed by any one of company l, l + 1, \dots, r. In other words, for an integer i which satisfies 1 \leq i \leq M, the pass enables the possessor to ride line i when l \leq C_i \leq r holds. It is possible to use a single pass for several lines. Let a ride pass (l, r) denote this ride pass.

Now, Q tourists, numbered from 1 to Q, visit La Paz. Tourist j (1 \leq j \leq Q) has a ride pass (L_j, R_j) and X_j boliviano cash.

Each tourist's goal is to ensure that no station cannot be travelled from station 1, using only lines that can be ridden with the ride pass he or she has. Tourist j (1 \leq j \leq Q) can exchange his or her ride pass described in the following process to achieve their goal. Here, each tourist can exchange at most once.

1. He or she chooses 2 integers l', r', which satisfy 1 \leq l' \leq r' \leq P.
2. He or she exchanges a ride pass (L_j, R_j) for a ride pass (l', r'). It costs |L_j - l'| + |R_j - r'| boliviano as a fee.

Your purpose is to determine, for each tourist, whether or not he or she can achieve his or her goal within the cash he or she has.

Write a program which, given information about stations, lines, and tourists, determines whether or not he or she can achieve his or her goal within the cash he or she has for each tourist.

Constraints

• 2 \leq N \leq 300\,000.
• 1 \leq M \leq 300\,000.
• 1 \leq P \leq 10^9.
• 1 \leq A_i < B_i \leq N (1 \leq i \leq M).
• 1 \leq C_i \leq P (1 \leq i \leq M).
• 1 \leq Q \leq 400\,000.
• 1 \leq L_j \leq R_j \leq P (1 \leq j \leq Q).
• 0 \leq X_j \leq 10^9 (1 \leq j \leq Q).
• Given values are all integers.

Subtasks

1. (7 points) N \leq 50, M \leq 50, Q \leq 50, X_j = 0 (1 \leq j \leq Q).
2. (8 points) P \leq 10.
3. (11 points) P \leq 100.
4. (23 points) P \leq 300\,000, X_j = 0 (1 \leq j \leq Q).
5. (9 points) P \leq 300\,000.
6. (22 points) N \leq 8\,000, M \leq 8\,000.
7. (20 points) No additional constraints.

Sample Input 1

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

Sample Output 1

Yes
No
No
Yes

First, tourist 1 has a ride pass (3, 7) and 0 boliviano cash initially. He or she can achieve his or her goal without exchange. Because, this pass enables tourist 1 to ride 4 lines, lines 1, 2, 3, 4, and he or she can move to each stations from station 1 by using these 4 lines as follows.

• It is possible to move as station 1 \rightarrow 2 by using line 3.
• It is possible to move as station 1 \rightarrow 2 \rightarrow 3 by using lines 1, 4 in this order.
• It is possible to move as station 1 \rightarrow 2 \rightarrow 4 by using lines 3, 2 in this order.

Therefore, output Yes on the 1-st line.

Next, tourist 2 has a ride pass (5, 6) and 0 boliviano cash initially. However, He or she can't achieve his or her goal. Because, this pass enables tourist 2 to ride 2 lines, lines 3, 4, and he or she can't move station 4 from station 1 by using these 2 lines. Moreover, since tourist 2 has only 0 boliviano as cash, he or she can't exchange the pass with another pass.

Hence, output No on the 2-nd line.

Also, tourist 3 can't achieve his or her goal, and tourist 4 can achieve his or her goal. Thus, output No on the 3-rd line, and output Yes on the 4-th line.

This sample input satisfies the constraints of all the Subtasks.

Sample Input 2

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

Sample Output 2

Yes
No
Yes

The information of stations and lines is the same as in the sample Input 1.

First, tourist 1 has a ride pass (5, 6) and 10 boliviano cash initially. He or she can achieve his or her goal with exchange as below.

1. He or she chooses 2 integers l' = 1, r' = 5, which satisfy 1 \leq l' \leq r' \leq P.
2. He or she exchange a ride pass (5, 6) for a ride pass (1, 5). It costs |5 - 1| + |6 - 5| = 5 boliviano as a fee.

Therefore, output Yes on the 1-st line.

Next, tourist 2 has a ride pass (3, 4) and 1 boliviano cash initially. He or she can't achieve his or her goal with any exchange.

Consequently, output No on the 2-nd line.

Since Tourist 3 can achieve his or her goal, output Yes on the 3-rd line.

This sample input satisfies the constraints of Subtasks 2,3,5,6,7.

Sample Input 3

3 1 1000000000
1 2 6
1
1 1000000000 1000000000

Sample Output 3

No

It is not possible to move from station 1 to station 3 with these lines, so tourists can't achieve their goal regardless of their ride passes.

This sample input satisfies the constraints of Subtasks 6,7.

Sample Input 4

5 9 2000
2 3 1814
2 3 457
1 2 1226
3 4 1354
1 5 1050
1 2 1725
2 3 1383
1 5 1626
1 4 1795
5
850 1872 128
82 428 1217
487 924 573
1639 1926 202
202 420 25

Sample Output 4

Yes
Yes
Yes
Yes
No

This sample input satisfies the constraints of Subtasks 5,6,7.

Problem Statement

Just Odd Inventions Co., Ltd. is a company renowned for doing "just odd inventions." Here we just call it JOI Company.

To celebrate the 5th anniversary of their flagship product, "Just Long Neckties," JOI Company has invented a new product: "Just Stretchable Neckties." As its name suggests, this new necktie has the unique feature of being able to extend its length indefinitely.

JOI Company has decided to hold a showcase event to promote the new necktie, and you have been selected as the host of the event. At the event, several models wearing the new neckties will appear on stage. Initially, the length of every necktie worn by the models is set to 1.

After that, you will carry out a total of N performances to demonstrate the necktie's stretchable feature to the audience. Each performance is conducted as follows:

1. First, you ask the audience to call out a number of their choice. Let this number be x.
2. Next, you decide whether to respond or ignore it.
   • If you choose to respond to it, you must select one of the models on stage whose necktie length is currently less than or equal to x and set the length of that model's necktie to exactly x. (Note that you may select a model whose necktie length is already x.) However, if no model can be selected, the showcase event will fail.
   • If you choose to ignore it, you do nothing.

However, if you ignore the audience's number two or more times in a row, the audience will get angry, and the showcase event will fail.

The number of models on stage, denoted as k (k\geq 1), has not yet been determined. Since hiring models costs considerable money, it is desirable to keep k as small as possible. The minimum value of k required to prevent the showcase event from failing depends on the numbers called out by the audience during the performances. Fortunately, you possess precognitive abilities and have foreseen that the number called out by the audience during the i-th performance (1\leq i\leq N) will be A_i.

Write a program which, given the numbers called out by the audience during the showcase event, calculates the minimum number of models k required to prevent the showcase event from failing.

Constraints

• 2 \leq N \leq 5\,000\,000.
• 1\leq A_i \leq 21 (1 \leq i \leq N).
• Given values are all integers.

Subtasks

1. (10 points) N\leq 15.
2. (6 points) N\leq 500, A_i \leq 2 (1 \leq i \leq N).
3. (12 points) N\leq 500, A_i \leq 5 (1 \leq i \leq N).
4. (18 points) N\leq 500, A_i \leq 15 (1 \leq i \leq N).
5. (26 points) N\leq 500\,000, A_i \leq 15 (1 \leq i \leq N).
6. (10 points) N\leq 500\,000.
7. (18 points) No additional constraints.

Sample Input 1

5
5 3 4 2 1

Sample Output 1

2

When k=2, the showcase event can be conducted as follows, for example:

• First, two models wearing the new neckties appear on stage. Initially, the length of each model's necktie is 1.
• During the 1st performance, the audience calls out 5. You ignore this.
• During the 2nd performance, the audience calls out 3. You respond to this by selecting the first model and setting their necktie length to 3. The necktie lengths of the two models are now 3 and 1, respectively.
• During the 3rd performance, the audience calls out 4. You respond to this by selecting the first model and setting their necktie length to 4. The necktie lengths of the two models are now 4 and 1, respectively.
• During the 4th performance, the audience calls out 2. You respond to this by selecting the second model and setting their necktie length to 2. The necktie lengths of the two models are now 4 and 2, respectively.
• During the 5th performance, the audience calls out 1. You ignore this.

When k=1, the showcase event will always fail. For example, if you respond to the audience's numbers during the 2nd, 3rd, and 4th performances as described above, the only model's necktie length becomes 4 after the 3rd performance. Then, at the 4th performance, you cannot select a model whose necktie length is less than or equal to 2, so the showcase event fails.

Hence, the minimum number of models k required to prevent the showcase event from failing is 2, and the output should be 2.

This sample input satisfies the constraints of Subtasks 1,3,4,5,6, and 7.

Sample Input 2

6
2 1 1 2 2 1

Sample Output 2

1

When k=1, the showcase event can be conducted as follows, for example:

• First, a model wearing the new necktie appear on stage. Initially, the length of the model's necktie is 1.
• During the 1st performance, the audience calls out 2. You ignore this.
• During the 2nd performance, the audience calls out 1. You respond to this by selecting the only model on stage and setting their necktie length to 1.
• During the 3rd performance, the audience calls out 1. You respond to this by selecting the only model on stage and setting their necktie length to 1.
• During the 4th performance, the audience calls out 2. You respond to this by selecting the only model on stage and setting their necktie length to 2.
• During the 5th performance, the audience calls out 2. You respond to this by selecting the only model on stage and setting their necktie length to 2.
• During the 6th performance, the audience calls out 1. You ignore this.

Note that in the example above, during the 2nd and 3rd performances, a model whose necktie length is already 1 is selected, and their necktie length is set to 1 again. Such a choice, where the necktie length does not change, is also allowed.

Hence, the minimum number of models k required to prevent the showcase event from failing is 1, and the output should be 1.

This sample input satisfies the constraints of all the subtasks.

\newline

Sample Input 3

10
2 4 6 7 4 5 5 3 4 1

Sample Output 3

3

This sample input satisfies the constraints of Subtasks 1,4,5,6, and 7.

Problem Statement

In the JOI country, there are N post offices, numbered from 1 to N.
Each post office has an assigned "destination," and the destination of post office i is post office P_i. Note that it is possible for P_i = i.
If a package is sent from post office i at time t, it will arrive at post office P_i at time t + 1. However, a post office cannot send another package while it is in the process of sending a package.
Each post office can store an unlimited number of packages at any given time.

Now, M packages need to be delivered in the JOI country.
The j-th package arrives at post office A_j at time 0, and it must eventually be delivered to the assigned post office B_j.
Given the information about the post offices and the packages, write a program to determine whether it is possible to deliver all the packages to their assigned post offices, and if so, find the smallest possible time at which the last package arrives at its assigned post office.

Constraints

• 2 \leqq N \leqq 200 \, 000.
• 1 \leqq M \leqq 200 \, 000.
• 1 \leqq P_i \leqq N (1 \leqq i \leqq N).
• 1 \leqq A_j, B_j \leqq N (1 \leqq j \leqq M).
• A_j \neq B_j (1 \leqq j \leqq M).
• Given values are all integers.

Subtasks

1. (3 points) N \leqq 3 \, 000， M = 1.
2. (9 points) N \leqq 3 \, 000， M \leqq 3 \,000.
3. (13 points) P = (1, 1, 2, \cdots, N-1), and \max(B_1, B_2, \dots, B_M) < \min(A_1, A_2, \dots, A_M).
4. (25 points) P = (1, 1, 2, \cdots, N-1).
5. (11 points) P = (N, 1, 2, \cdots, N-1).
6. (25 points) P_1 = 1, P_i < i (2 \leqq i \leqq N).
7. (14 points) No additional constraints.

Sample Input 1

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

Sample Output 1

3

For example, by sending the packages in the following way, all the packages can be delivered to their assigned post offices by time 3:

• At time 0, packages 1, 2, and 3 are at post office 3. Send package 2 to post office 2.
• At time 1, package 2 is at post office 2, and packages 1 and 3 are at post office 3. From post office 2, send package 2 to post office 1, and from post office 3, send package 3 to post office 2.
• At time 2, package 2 is at post office 1, package 3 is at post office 2, and package 1 is at post office 3. From post office 2, send package 3 to post office 1, and from post office 3, send package 1 to post office 2.
• At time 3, packages 2 and 3 are at post office 1, and package 1 is at post office 2. At this point, all the packages have reached their destinations.

Since it is not possible to deliver all the packages to their assigned post offices by time 2, output 3.

This sample input satisfies the constraints of Subtasks 2, 3, 4, 6, 7.

Sample Input 2

3
2 1 3
1
1 3

Sample Output 2

-1

No matter how the packages are sent, it is impossible to deliver a package from post office 1 to post office 3, so output -1.

This sample input satisfies the constraints of Subtasks 1, 2, 7.

Sample Input 3

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

Sample Output 3

5

This sample input satisfies the constraints of Subtasks 2, 4, 6, 7.

Sample Input 4

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

Sample Output 4

4

This sample input satisfies the constraints of Subtasks 2, 5, 7.

Sample Input 5

7
1 1 1 3 3 4 4
5
6 1
6 3
7 1
5 1
5 1

Sample Output 5

5

This sample input satisfies the constraints of Subtasks 2, 6, 7.

Sample Input 6

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

Sample Output 6

6

This sample input satisfies the constraints of Subtasks 2, 7.