Maiden Reincarnation Grand Contest 002

A. How to Survive a Game of Old Maid

Hilda, the maid, ends up passing through the village of Hinamizawa during her travels. The locals have an unusual custom: all grudges and disputes can only be settled through a game.

Mion, the barkeep at the tavern, finds that Hilda did not bring enough money to cover her own tab. Since Mion is generous, she will cover the remaining balance and allow Hilda to leave — but only if Hilda can defeat her in a game of Old Maid.

In the card game Old Maid, the goal is to get rid of your cards by finding matching pairs and discarding them. The player left holding the single, unpaired card at the end of the game is the "Old Maid".

You are given an array of \( n \) integers representing the cards in your hand. In this deck, every number appears exactly twice (forming a matching pair), except for exactly one number which appears only once.

Help Hilda win the game by finding the value of the single remaining number — the Old Maid!

Input

The first line contains an integer \( n \) \( (1 ≤ n ≤ 10^4) \) — the size of the deck.

The second line contains \( n \) integers \( a_1, a_2, ..., a_n \) \( (0 ≤ a_i ≤ 10^5) \) — the values of the cards. Every integer appears exactly twice, except for one integer which appears only once.

Output

Print a single integer — the value of the unpaired card (Old Maid).

Example

Input

5
4 7 2 4 2

Output

7

Input

1
5

Output

5

Explanation

In the first example, the \( 2 \)'s and \( 4 \)'s form pairs and are removed. The number \( 7 \) has no pair and is left over.

In the second example, there is only one card, so it is immediately the Old Maid.

B. Trouble on the Orient Express

Erika, the detective, is waiting at a train platform, trying to figure out if the ticket she just bought for the Orient Express will take her to the Northern Duke's Mansion — the location of her next case.

The train travels strictly in one direction along a specific path. This path is represented by an array of strings \( s \), where \(s_i\) is the name of the \( i \)-th station on the trip.

Erika has purchased a zone ticket that allows her to travel a maximum of \( k \) stops from where she boarded.

Given the route array \( s \), the boarding station \( b \), the destination station \( d \), and the max stop limit \( k \) on the ticket, determine if Erika's ticket is valid.

A ticket is considered valid if and only if the following conditions are met:

1. Both the boarding station and the destination station exist on the route.

2. The destination station appears after the boarding station on the route (the train only goes one way!).

3. The number of stops traveled (the difference between their indices) is less than or equal to the max stop limit.

Input

The first line contains an integer \( k \) \( (1 ≤ k ≤ 100) \) — the maximum number of stops indicated on the ticket.

The second line contains a string \( b \) — the name of the boarding station.

The third line contains a string \( d \) — the name of the destination station.

The fourth line contains an integer \( n \) \( (1 ≤ n ≤ 100) \) — the number of stops on the route.

The next \( n \) lines each contain a single string \( s_i \) — the name of the \( i \)-th station on the route, in order. All names on the route are unique.

Each name is a string of English letters, length between \( 1 \) and \( 20 \).

Output

Print true if Erika's train ticket is valid. Otherwise, print false.

Example

Input

2
Rokkenjima
Wyverngarde
5
Aincrad
Rokkenjima
Penacony
Wyverngarde
IcewindDale

Output

true

Input

2
Red
Crystal
3
Red
Blue
Yellow

Output

false

Input

3
Cyoria
Barovia
5
Barovia
Westeros
Cyoria
Sorcier
Narnia

Output

false

Explanation

In Example 1, you board at "Rokkenjima" (index \( 1 \)) and get off at "Wyverngarde" (index \( 3 \)). The destination is after the boarding station. The number of stops traveled is \( 3 - 1 = 2 \). Because \( 2 ≤ k = 2 \) (the number of max stops), your ticket is valid.

In Example 2, "Crystal" is not a station on the route, so the ticket is invalid.

In Example 3, "Barovia" (index \( 0 \)) appears before "Cyoria" (index \( 2 \)). Since this train only goes in one direction, you cannot reach your destination.

C. The Great Court of Illusions

Luna, the attorney, has been summoned to the Great Court of Illusions. She must defend her client — the villainess, Artezia — in a trial. Battler, the lead prosecutor, has prepared a number of witnesses that he hopes will be sufficient to prove Artezia's involvement in the crime.

Luna is given a transcript of the current witness' testimony, represented as an array \( a \) of length \( n \) of non-zero integers.

The testimony is a timeline of statements about different suspects:

A positive integer \( x \) means the witness claims: "I saw suspect \( x \) at the scene."

A negative integer \( -x \) means the witness claims: "I did NOT see suspect \( x \) at the scene."

The jury will only believe a contiguous segment of the testimony if it is credible. A segment of testimony is considered credible if it contains absolutely no contradictions. A contradiction occurs if a segment contains both a claim that suspect \( x \) was there (\( x \)) and a claim that suspect \( x \) was not there (\( -x \)).

(Note: A witness repeating the exact same claim, such as \( [2, 3, 2] \), is just them reinforcing their story and is NOT considered a contradiction.)

To destroy the witness' case, you want to point out how little of their story actually makes sense. Help Luna win the trial by finding the length of the longest credible contiguous segment of the testimony.

Input

The first line contains an integer \( n \) \( (1 ≤ n ≤ 10^5) \) — the number of statements in the testimony.

The second line contains \( n \) space-separated integers \( a_1, a_2, ..., a_n \) \( (-10^5 ≤ a_i ≤ 10^5, a_i ≠ 0) \) — the statements made by the witness.

Output

Print a single integer — the length of the longest credible contiguous segment of the testimony.

Example

Input

6
1 2 3 -2 4 1

Output

4

Input

5
7 8 7 8 9

Output

5

Explanation

In the first example, the longest credible segment is \( [3, -2, 4, 1] \) with a length of \( 4 \).

In the second example, the witness repeats themself, but never contradicts themself, so the entire array is credible.

D. The Duchess' Tea Party

Duchess Chloé is hosting an exclusive tea party for the local high society. She has invited \( n \) guests, including the esteemed Lady Lambda, and she has exactly one large circular table with \( n \) seats.

Each guest has a social standing, represented by an integer array \( a \) of length \( n \), where \(a_i\) is the prestige of the \( i \)-th guest at the party.

High-society guests are very particular about who they sit next to. If two adjacent guests have vastly different prestige levels, it creates a palpable, awkward tension. The awkwardness of a seating arrangement is defined as the maximum absolute difference in prestige between any two adjacent guests at the table.

Since the table is circular, the guest sitting in the last seat is adjacent to the guest sitting in the first seat.

Find the minimum possible awkwardness Chloé can achieve by rearranging the guests' seats optimally.

Input

The first line contains an integer \( n \) \( (3 ≤ n ≤ 10^5) \) — the number of guests.

The second line contains \( n \) space-separated integers \( a_1, a_2, ..., a_n \) \( (1 ≤ a_i ≤ 10^9) \) — the prestige values of the guests.

Output

Print a single integer — the minimum possible awkwardness value of the optimal seating arrangement.

Example

Input

4
1 5 8 9

Output

7

Input

3
10 10 10

Output

0

Explanation

In the first example, an optimal seating arrangement is \( [1, 8, 9, 5] \). The maximum difference (awkwardness) is \( 7 \). It is impossible to achieve an awkwardness lower than \( 7 \).

In the second example, all guests have the exact same prestige. There is no tension at all, so the awkwardness is \( 0 \).

E. SSS-Class Raging Loop Hunter

Kim Gong-ja is a Seer trapped in a mysterious time loop. He is forced to play the game of Werewolf over and over with the same group of villagers.

After a number of loops, he has finally identified that there are \( w \) wolves in the village (with IDs from \( 0 \) to \( w - 1 \)). To break the loop, he must witness each of the \( w \) wolves performing a "suspicious action" at least once.

Gong-ja has a notebook that predicts every suspicious wolf action that will happen tonight. The notebook provides a list of \( n \) observations, where the \( i \)-th observation is defined by two integer values:

\( t_i \) — the time that the suspicious action occurs.

\( m_i \) — the ID of the wolf that performed the suspicious action.

Gong-ja wants to stay "Active" for the shortest possible continuous duration. He can choose any start time \( t_\text{start} \) and any end time \( t_\text{end} \). He will witness every observation where \( t_\text{start} ≤ t_i ≤ t_\text{end} \).

Find the minimum possible duration (\( t_\text{end} - t_\text{start} \)) such that Gong-ja witnesses at least one suspicious action from every one of the \( w \) wolves.

Input

The first line contains an integer \( w \) \( (1 ≤ w ≤ 10^5) \) — the number of wolves in the village.

The second line contains an integer \( n \) \( (w ≤ n ≤ 10^5) \) — the number of observations in the notebook.

The next \( n \) lines each contain two space-separated integers \( t_i, m_i \) \( (0 ≤ t_i ≤ 10^9, 0 ≤ m_i < w) \) — the time and the wolf ID for that observation. All time values are unique.

Output

Print a single integer — the minimum duration required to observe all wolves at least once.

Example

Input

3
5
10 0
20 1
25 0
30 2
40 1

Output

10

Explanation

If you choose the window from \( t_a = 20 \) to \( t_b = 30 \):

At \( t = 20 \), you see Wolf \( 1 \).

At \( t = 25 \), you see Wolf \( 0 \).

At \( t = 30 \), you see Wolf \( 2 \).

You have seen all \( 3 \) wolves. The duration is \( 30 - 20 = 10 \). This is the shortest possible duration.

F. Villainess Level 99

Yumiella may be the hidden boss, but she's not the Demon Lord. To prevent her own downfall in the future, she needs to level up as quickly as possible before the academy arc begins.

She begins the story with \( 0 \) XP and \( 0 \) Power. Her goal is to reach a total of \( t \) experience points as quickly as possible.

There are \( n \) unique quests available in the story. The \( i \)-th quest is defined by four integer values:

\( a_i \) — the minimum power required to start the quest.

\( b_i \) — the amount of XP gained upon completion.

\( c_i \) — the amount of permanent power gained upon completion.

\( d_i \) — the time (in minutes) it takes to complete the quest.

Yumiella can complete quests in any order, provided she meets the minimum power requirement at the time that she starts the quest. Each quest can only be completed once.

Help her find the minimum total time required to reach at least \( t \) XP. If it is impossible to reach the target XP with the available quests, return \( -1 \).

Input

The first line contains an integer \( t \) \( (1 ≤ t ≤ 500) \) — the target XP.

The second line contains an integer \( n \) \( (1 ≤ n ≤ 100) \) — the number of available quests.

The next \( n \) lines each contain four space-separated integers \( a_i, b_i, c_i, d_i \) \( (0 ≤ a_i ≤ 500, 1 ≤ b_i ≤ 500, 0 ≤ c_i ≤ 500, 1 ≤ d_i ≤ 10^6) \) — the values defining the quest.

Output

Print a single integer — the minimum total time required to reach the target XP. If it is impossible, print \( -1 \).

Example

Input

100
3
0 10 10 5
0 20 1 10
10 90 5 20

Output

25

Input

200
2
10 10 10 10
5 20 1 5

Output

-1

Explanation

In the first example, the optimal strategy is to complete quest \( 1 \), then quest \( 3 \). The time taken is \( 25 \) minutes.

In the second example, it is impossible for Yumiella to complete any quests, so the target XP cannot be reached.

G. Pre-Dinner Service Damage Control

Lady Kanna is placed in charge of the dinner service at the Addis Estate. The head chef, Gordon, has called out sick, so it is up to Kanna to manage the dinner service, which is being attended by many high-ranking nobles.

The dinner rush has just begun, and Kanna has a rail full of order tickets that need to be cooked.

You are given an integer array of orders \( a \), where \( a_i \) represents the time in minutes it takes to cook the \( i \)-th dish. There are \( k \) identical line cooks available to help you prepare the food.

Because the tickets are printed on a single continuous rail, the dishes must be cooked in the exact order they appear. You must divide the rail of tickets into \( k \) contiguous segments and assign one segment to each line cook.

All \( k \) line cooks will start cooking at the exact same time and will cook their assigned dishes sequentially. The dinner service is considered complete when all cooks have finished their assigned segments of dishes.

As the head chef, Kanna's goal is to delegate the tickets to minimize the total time it takes to finish all the orders. Help her find the minimum possible time required to complete the dinner service.

Input

The first line contains an integer \( k \) \( (k ≤ n) \) — the number of line cooks.

The second line contains an integer \( n \) \( (1 ≤ n ≤ 10^5) \) — the number of orders.

The third line contains \( n \) space-separated integers \( a_1, a_2, ..., a_n \) \( (1 ≤ a_i ≤ 10^4) \) — the time needed to cook each order.

Output

Print a single integer — the minimum possible time required to complete the dinner service, in minutes.

Example

Input

2
5
7 2 5 10 8

Output

18

Input

3
3
15 10 12

Output

15

Explanation

In the first example, the optimal allocation is \( [7, 2, 5] \) and \( [10, 8] \), which results in a minimum service time of \( 18 \) minutes.

In the second example, since you have \( 3 \) cooks and \( 3 \) orders, the optimal strategy is to assign exactly one order to each cook. The service will finish when the longest dish is completed, which takes \( 15 \) minutes.

Help: Standard Input/Output

In programming competitions, problems usually require you to read from standard input and write to standard output.

What is Standard Input?

This is the input your program reads from the console. You don't need to open any files or create a GUI. Just read using language-specific commands like cin (C++) or input() (Python).

What is Standard Output?

This is where your program writes its answers — again, through the console. Use commands like cout (C++) or print() (Python). Make sure the output matches the required format exactly.

Sample Problem:

Given two integers \( A \) and \( B \), print their sum.

Input

6 7

Output

13

Sample Solution Template

In C++

#include <iostream>
using namespace std;

int main() {
    int A, B;
    cin >> A >> B; // Read two integers
    cout << A + B << "\n"; // Print their sum
    return 0;
}

In Python

# Read input, split by space, convert to int
A, B = map(int, input().split())
print(A + B)