Yandex.Algorithm 2018, final round
A. Smart Vending
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

It is a hot Sunday afternoon on a streets of Saint-Petersburg. However, Yandex intern Arcadiy is in the office doing some final edits in his student graduation work. After several hours of a hard work he decided to chill and went to a vending machine downstairs to buy some bottles of his favorite soft drink Kvas-Klass.

This vending machine is very special. It only accepts coins of one ruble and banknotes of one million rubles, and it only sells Kvas-Klass that costs r rubles per bottle. Arcadiy has b banknotes of one million rubles and c coins of one ruble. Initially, vending machine is loaded with d coins that it can use to provide change. The process of buying a single bottle of this fantastic drink goes as follows.

  1. Arcadiy inserts some number of banknotes x and some number of coins y. Thus, the total amount of money loaded is z = 106·x + y.
  2. Then he presses purchase button. If z is less than r he is asked to put more money inside the machine.
  3. If z is greater than or equal to r machine tries to give a change to Arcadiy. Change can only be given with coins, so the number of one ruble coins inside the machine (coins loaded in the machine during this purchase are not considered) should be at least z - r. If the number of coins is insufficient the purchase won't happen.
  4. If z ≥ r and the number of coins is sufficient to give change (or change is not required, i.e. z = r) the purchase happens. Vending machine takes x banknotes and y coins (that now can used to provide change for next purchases), returns z - r coins back to Arcadiy and gives him a bottles of desired drink.

Arcadiy only wants to purchase a single bottle, but he is a programmer after all. Now he wonders, what is the maximum possible number of bottles he can buy if he picks an optimal purchase strategy? You may assume the vending machine has infinite number of bottles of Kvas-Klass (that is unfortunately never a case in a real life).

Input

The first line of the input contains two integers b and c (0 ≤ b, c ≤ 109) — the number of one million ruble banknotes and the number of one ruble coins Arcadiy initially possesses.

The second line of the input contains two integers r and d (1 ≤ r ≤ 109, 0 ≤ d ≤ 109) — the price of one bottle of Kvas-Klass and the number of coins in the vending machine at the beginning. Note that the number of banknotes inside the machine doesn't matter.

Output

Print one integer — the maximum number of bottles of Kvas-Klass Arcadiy can buy if he selects an optimal strategy.

Examples
Input
21 1000000
1100000 0
Output
20
Input
10 700000
350000 200000
Output
4
Note

In the first sample, Arcadiy can spend all the money he has.

In the second sample, he can first buy two bottles using only the coins he has. Then he buys a bottle with a banknote (there are 900 000 coins inside the machine at this moment so it can give a change). Finally he buys one more bottle.

B. LIS vs. LDS
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

A longest increasing subsequence (LIS) of an array a1, ..., an is a sequence of indices 1 ≤ i1 < ... < ik ≤ n such that ai1 < ... < aik, and k is largest possible. Longest decreasing subsequence (LDS) can be defined similarly.

A brand new Yandex interview problem asks you to take a permutation p = (p1, ..., pn) of numbers 1, 2, ..., n, and find an LIS and an LDS of the permutation that do not share common elements, or report that it is impossible. Formally, you have to find two sequences of indices i1 < ... < ik and j1 < ... < jl so that:

  • ai1 < ... < aik;
  • bj1 > ... > bjl;
  • k is the length of LIS of p;
  • l is the length of LDS of p,
  • all indices i1, ..., ik, j1, ..., jl are distinct.
Input

The first line contains an integer n (1 ≤ n ≤ 500 000) — the size of the permutation p.

The second line contains n distinct integers p1, p2, ..., pn (1 ≤ pi ≤ n).

Output

If an answer exists, print four lines. The first line should contain a single integer k — the size of LIS of the permutation p. The second line should contain k integers i1, ..., ik satisftying 1 ≤ i1 < ... < ik ≤ n and ai1 < ... < aik. The next two lines should describe an LDS (j1, ..., jl) of p in the same format. All indices i1, ..., ik, j1, ..., jl should be distinct.

If there is no answer, print "texttt{IMPOSSIBLE}" (without the quotes) in the only line of the output.

Examples
Input
4
2 4 1 3
Output
2
1 4 
2
2 3
Input
4
3 4 1 2
Output
IMPOSSIBLE
Note

In the second sample, the length of both LIS and LDS is 2. Here are all possible LIS: (1, 2), (3, 4) (indices of elements are given, not their values); and all possible LDS: (1, 3), (1, 4), (2, 3), (2, 4). Each LIS has a common element with each LDS, hence there is no answer.

C. Eat And Walk
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Eugene works at Yandex as a data scientist. Recently he decided to rest for a while so he took vacation and went to a wonderful education center on the shore of the Black sea where he teaches machine learning and data analysis to high school students.

Every evening he goes to the shore where n nice restaurants are located. Restaurants are numbered with consecutive integers 1, 2, ..., n, the i-th restaurant is located at position i. Eugene starts at position 0 and with e units of energy. Initially his stomach is empty and it takes him only one unit of energy to change his position by 1 (for example, to go from position 0 to position 1 where restaurant 1 is located). The evening will proceed as follows.

  1. If at some moment of time Eugene is located at position i and he already ate x units of food during this evening, he can move to positions i - 1 or i + 1 by spending x + 1 units of energy.
  2. If he is now at position i between 1 and n inclusive and he hasn't visited restaurant i during this evening, he can choose to go there. He knows that will result him eating exactly ai units of food. This action is free in terms of units of energy (chewing is not counted).
  3. If at some moment of time Eugene is at position 0 he may choose to stop at go back to educational center. This won't cost him any units of energy.

As Eugene does machine learning and all the stuff it is up to you to compute, what is the maximum number of units of food he can eat during this evening and return to educational center at position 0 if he behaves optimal?

Input

The first line of the input contains two integers n and e (1 ≤ n ≤ 200, 000, 1 ≤ e ≤ 107) — the number of restaurants along the shore and the initial amount of Eugene's energy.

The second line contains n integers a1, a2, ..., an (0 ≤ ai ≤ 1 000 000), the i-th of them denoting the exact number of units of food Eugene will eat if he chooses to visit restaurant i.

Output

Print one integer equal to the maximum possible number of units of food Eugene can eat this evening.

Examples
Input
5 100
1 1 1 1 1
Output
5
Input
4 25
3 30 1 3
Output
6
Note

In the first sample Eugene has a lot of energy, so he just walks from position 0 to position 5 visiting every restaurant on his path. The he goes back to education center at position 0.

In the second sample Eugene should first go to the 4-th restaurant, then visit restaurant 1 and finally go back to position 0.

D. Search Engine
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

As you probably know, the main product of Yandex is its search engine, which we will consider in this problem.

In this problem, search engine operates on a database, which can be represented as a string s of length n. The System allows users to search arbitrary text in a database, as a result of the search, system displays a list of request's occurrences, alongside the number of them. An occurrence means that query text appears in a database as a substring.

Alice is bored, and so she tries to entertain herself. She has opened the search engine, which shows the empty text field initially.

Then Alice repeatedly modifies the previous request by either appending or prepending a new letter to it, and then she repeats the search. Alice performs this operation exactly n times.

The entertaining part of the process is observation process of the number of occurencies displayed by the system — it may decrease a lot after one iteration. Or may not.

Alice decided to test whether the search engine will continue to work fast if required to output a lot of data, so she decided to make her requests in such a way that the sum of occurrences of all n requests in s will be maximum possible. What is the largest possible sum she can achieve?

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 200 000) — the length of the string s.

The second line contains the string s composed of English lowercase letters only.

Output

Output a single integer — largest possible total number of occurences.

Examples
Input
5
aaaaa
Output
15
Input
6
abcabc
Output
9
Note

The request sequence "a"  →  "aa"  →  "aaa"  →  "aaaa"  →  "aaaaa" gives the total number of 15 = 1 + 2 + 3 + 4 + 5 occurrences.

One of the optimal sequences for the second sample is "a"  →  "ab"  →  "abc"  →  "cabc"  →  "bcabc"  →  "abcabc" gives 9 = 2 + 2 + 2 + 1 + 1 + 1 occurrences in total.

E. Guess Me If You Can
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

This is an interactive problem.

Alice is a voice assistant recently introduced by Yandex. One of the directions to extend its functionality is to add different games that Alice can play with the users if they are bored. The game we are interested in has the following rules.

  1. At the beginning Alice tells you some number n and thinks of some permutation of integers from 1 to n denoted as p1, p2, ..., pn.
  2. Your goal is to tell Alice where is the element equal to n located in the original permutation.
  3. The only operation the other player has is to select some position i. After that Alice increases pi by one and reports the number of distinct elements in the current array p1, p2, ..., pn.

The game has different difficulty levels. The last level asks you to tell the position of n in original permutation in just 50·n questions. You are now working on your own voice assistant Boris and you want to teach it play this game, so you can put two phones next to each other as watch the battle.

Interaction

At the beginning Alice tells you the value of n (1 ≤ n ≤ 1000). Then, you can ask no more than 50·n questions of the form: "0 x", where 0 means that you are asking a question and x should be from 1 to n inclusive marking that Alice should increase px by one and report you the number of distinct elements in array p.

As soon as you are confident with the answer (or ran out of questions available) you must print: "1 x", where 1 means that you are reporting the answer and x is the answer itself, i.e. you claim that px = n was true at the beginning of the game. Your program must finish as soon as you print the answer. Otherwise you might get inappropriate judging verdict.

Example
Input
5
1 5 2 4 3
Output
2
Note

The input sample section shows you a valid test case. First integer stands for the size of the permutation and then follows the permutation itself. One of the possible interaction scenarios looks as follows: 


5
        0 1
4
        0 1
4
        0 3
3
        0 4
2
        1 2
Lines with two integers correspond to possible program outputs, while lines with one integer stand for the input your program should read.

F. Lazy Hash Table
time limit per test
7 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Yandex engineer Ivan is a very tidy person, he is among people who always create an array of size exactly they need.

Today Ivan has n distinct positive integers a1, a2, ..., an he would like to put in a hash table. He wants to pick some integer m — the number of buckets and then send integer x to bucket . So, a1 goes to bucket h(a1), a2 goes to bucket h(a2) and so on. As much as Ivan loves order, Ivan hates collisions. He wants to pick m in such a way that each bucket contains at most one integer. In other words, Ivan wants to choose m such that all are distinct. Please find such m. As one of the goals of a data infrastructure engineer is to be as efficient as possible, Ivan wants you to find minimum possible valid value of m.

Input

The first line of the input contains one integer n (1 ≤ n ≤ 2 000 000) — the number of integers Ivan possesses. The next line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 2 000 000). It is guaranteed that all elements of sequence a are distinct.

Output

Print one integer — the minimum possible value of m such that all values will be distinct.

Examples
Input
3
1 2 3
Output
3
Input
3
1 2 4
Output
4
Input
5
1 3 6 10 15
Output
8