vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Ringo found a string $s$ of length $n$ in his yellow submarine. The string contains only lowercase letters from the English alphabet. As Ringo and his friends love palindromes, he would like to turn the string $s$ into a palindrome by applying two types of operations to the string. 

The first operation allows him to choose $i$ ($2 \le i \le n-1$) and to append the substring $s_2s_3 \ldots s_i$ ($i - 1$ characters) reversed to the front of $s$.

The second operation allows him to choose $i$ ($2 \le i \le n-1$) and to append the substring $s_i s_{i + 1}\ldots s_{n - 1}$ ($n - i$ characters) reversed to the end of $s$.

Note that characters in the string in this problem are indexed from $1$.

For example suppose $s=$abcdef. If he performs the first operation with $i=3$ then he appends cb to the front of $s$ and the result will be cbabcdef. Performing the second operation on the resulted string with $i=5$ will yield cbabcdefedc.

Your task is to help Ringo make the entire string a palindrome by applying any of the two operations (in total) at most $30$ times. The length of the resulting palindrome must not exceed $10^6$

It is guaranteed that under these constraints there always is a solution. Also note you do not have to minimize neither the number of operations applied, nor the length of the resulting string, but they have to fit into the constraints.


-----Input-----

The only line contains the string $S$ ($3 \le |s| \le 10^5$) of lowercase letters from the English alphabet.


-----Output-----

The first line should contain $k$ ($0\le k \le 30$)  — the number of operations performed.

Each of the following $k$ lines should describe an operation in form L i or R i. $L$ represents the first operation, $R$ represents the second operation, $i$ represents the index chosen.

The length of the resulting palindrome must not exceed $10^6$.


-----Examples-----
Input
abac

Output
2
R 2
R 5

Input
acccc

Output
2
L 4
L 2

Input
hannah

Output
0


-----Note-----

For the first example the following operations are performed:

abac $\to$ abacab $\to$ abacaba

The second sample performs the following operations: acccc $\to$ cccacccc $\to$ ccccacccc

The third example is already a palindrome so no operations are required.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Inna and Sequence 

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Dima's spent much time thinking what present to give to Inna and gave her an empty sequence *w*. Now they want to fill sequence *w* with numbers zero and one. For that, they decided to play an amusing game. 

Before the game begins, Dima chooses *m* integers *a*1,<=*a*2,<=...,<=*a**m* (1<=≤<=*a*1<=&lt;<=*a*2<=&lt;<=...<=&lt;<=*a**m*). Then Inna and Dima start playing, that is, adding numbers to sequence *w*. Each new number they choose is added to the end of the sequence. At some moments of time Dima feels that the game is going to end too soon (and he wants to play with Inna as long as possible), so he hits a table hard with his fist. At that the *a*1-th, *a*2-th, *a*3-th, ..., *a**k*-th numbers from the beginning simultaneously fall out of the sequence (the sequence gets *k* numbers less). Here *k* is such maximum number that value *a**k* doesn't exceed the current length of the sequence. If number *a*1 is larger than the current length of *w*, then nothing falls out of the sequence.

You are given the chronological sequence of events in the game. Each event is either adding a number to the end of sequence *w* or Dima's hit on the table. Calculate the sequence *w* after all these events happen.

Input Specification:
The first line of the input contains two integers *n* and *m* (1<=≤<=*n*,<=*m*<=≤<=106) showing how many events took place and how many numbers Dima chose.

The next line contains *m* distinct integers *a**i* (1<=≤<=*a**i*<=≤<=106) sorted in the increasing order. 

Next *n* lines describe the events in the chronological order. Each line contains a single integer: -1, 0 or 1. Number -1 means that Dima hits the table. Number 0 means that Inna and Dima add number 0 to the end of the sequence. Number 1 means that Inna and Dima add number 1 to the end of the sequence.

Output Specification:
In a single line print a sequence of numbers 0 and 1 — the elements of the sequence after all events happen. Print the elements of the sequence in the order from the beginning to the end of the sequence.

If after all events the sequence ends up empty, print "Poor stack!".

Demo Input:
['10 3\n1 3 6\n-1\n1\n1\n0\n0\n-1\n0\n1\n-1\n1\n', '2 1\n1\n1\n-1\n']

Demo Output:
['011\n', 'Poor stack!\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The ICC Cricket World Cup 2015 fever is rising up day by day as India is consistently beating every strong team of the world. Fans of the Indian Cricket Team also say that it is not just World Cup, it is the World against India.

The next match of India is semi final with Australia on March 26, 2015. So Australia knowing that Indian Cricket team has the most passionate, aggressive and skilled players has fear of losing in the semi finals and has sent a delegate to negotiate with the Coach of the Indian Cricket team. The Australian delegate tried as hard as he could to convince the Indian Coach but the Indian Coach resisted all the time. 

But then suddenly the coach had a thought in his mind that her daughter Tanya was stuck in a programming assignment and had asked the delegate to get the programming assignment of her daughter done. The coach will only rethink about negotiation if the delegate gets the programming assignment of her daughter done.

The programming assignment is as follows:
Tanya was given an array 'a' of positive integers of size n by her teacher and asked to find the length of the longest increasing subsequence of the array with the property that no 2 adjacent elements of the subsequence shall be co-prime.

You are a renowned programmer of Australia, whom your delegate friend has asked to solve the programming assignment. Help your delegate friend in completing Tanya's assignment, and making Australia win the semi-finals.

Input

The first line of input consists of a single integer n, denoting the size of the given array.
The next line has n positive integers, each separated by a single space, denoting the array elements. For every array index i such that 2 ≤ i ≤ n, a[i-1] < a[i] .

Output:

Output the length of the longest strictly increasing subsequence fulfilling the special condition.

Constraint:

1 ≤ n ≤ 10^5

1 ≤ a[i] ≤ 10^5

SAMPLE INPUT
6
1 2 3 4 5 6

SAMPLE OUTPUT
3

Explanation

The subsequence is 2, 4, 6 and hence it's length is 3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Boy Dima gave Julian a birthday present — set B consisting of positive integers. However, he didn't know, that Julian hates sets, but enjoys bipartite graphs more than anything else!

Julian was almost upset, but her friend Alex said, that he can build an undirected graph using this set in such a way: let all integer numbers be vertices, then connect any two i and j with an edge if |i - j| belongs to B.

Unfortunately, Julian doesn't like the graph, that was built using B. Alex decided to rectify the situation, so he wants to erase some numbers from B, so that graph built using the new set is bipartite. The difficulty of this task is that the graph, Alex has to work with, has an infinite number of vertices and edges! It is impossible to solve this task alone, so Alex asks you for help. Write a program that erases a subset of minimum size from B so that graph constructed on the new set is bipartite.

Recall, that graph is bipartite if all its vertices can be divided into two disjoint sets such that every edge connects a vertex from different sets.

Input

First line contains an integer n ~ (1 ⩽ n ⩽ 200 000) — size of B

Second line contains n integers b_1, b_2, …, b_n ~ (1 ⩽ b_i ⩽ 10^{18}) — numbers of B, all b_i are unique

Output

In the first line print single integer k – the number of erased elements. In the second line print k integers — values of erased elements.

If there are multiple answers, print any of them.

Examples

Input


3
1 2 3


Output


1
2 

Input


2
2 6


Output


0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alice got an array of length n as a birthday present once again! This is the third year in a row! 

And what is more disappointing, it is overwhelmengly boring, filled entirely with zeros. Bob decided to apply some changes to the array to cheer up Alice.

Bob has chosen m changes of the following form. For some integer numbers x and d, he chooses an arbitrary position i (1 ≤ i ≤ n) and for every j ∈ [1, n] adds x + d ⋅ dist(i, j) to the value of the j-th cell. dist(i, j) is the distance between positions i and j (i.e. dist(i, j) = |i - j|, where |x| is an absolute value of x).

For example, if Alice currently has an array [2, 1, 2, 2] and Bob chooses position 3 for x = -1 and d = 2 then the array will become [2 - 1 + 2 ⋅ 2,~1 - 1 + 2 ⋅ 1,~2 - 1 + 2 ⋅ 0,~2 - 1 + 2 ⋅ 1] = [5, 2, 1, 3]. Note that Bob can't choose position i outside of the array (that is, smaller than 1 or greater than n).

Alice will be the happiest when the elements of the array are as big as possible. Bob claimed that the arithmetic mean value of the elements will work fine as a metric.

What is the maximum arithmetic mean value Bob can achieve?

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 10^5) — the number of elements of the array and the number of changes.

Each of the next m lines contains two integers x_i and d_i (-10^3 ≤ x_i, d_i ≤ 10^3) — the parameters for the i-th change.

Output

Print the maximal average arithmetic mean of the elements Bob can achieve.

Your answer is considered correct if its absolute or relative error doesn't exceed 10^{-6}.

Examples

Input

2 3
-1 3
0 0
-1 -4


Output

-2.500000000000000


Input

3 2
0 2
5 0


Output

7.000000000000000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
XXI Berland Annual Fair is coming really soon! Traditionally fair consists of $n$ booths, arranged in a circle. The booths are numbered $1$ through $n$ clockwise with $n$ being adjacent to $1$. The $i$-th booths sells some candies for the price of $a_i$ burles per item. Each booth has an unlimited supply of candies.

Polycarp has decided to spend at most $T$ burles at the fair. However, he has some plan in mind for his path across the booths:  at first, he visits booth number $1$;  if he has enough burles to buy exactly one candy from the current booth, then he buys it immediately;  then he proceeds to the next booth in the clockwise order (regardless of if he bought a candy or not). 

Polycarp's money is finite, thus the process will end once he can no longer buy candy at any booth.

Calculate the number of candies Polycarp will buy.


-----Input-----

The first line contains two integers $n$ and $T$ ($1 \le n \le 2 \cdot 10^5$, $1 \le T \le 10^{18}$) — the number of booths at the fair and the initial amount of burles Polycarp has.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) — the price of the single candy at booth number $i$.


-----Output-----

Print a single integer — the total number of candies Polycarp will buy.


-----Examples-----
Input
3 38
5 2 5

Output
10

Input
5 21
2 4 100 2 6

Output
6



-----Note-----

Let's consider the first example. Here are Polycarp's moves until he runs out of money:  Booth $1$, buys candy for $5$, $T = 33$;  Booth $2$, buys candy for $2$, $T = 31$;  Booth $3$, buys candy for $5$, $T = 26$;  Booth $1$, buys candy for $5$, $T = 21$;  Booth $2$, buys candy for $2$, $T = 19$;  Booth $3$, buys candy for $5$, $T = 14$;  Booth $1$, buys candy for $5$, $T = 9$;  Booth $2$, buys candy for $2$, $T = 7$;  Booth $3$, buys candy for $5$, $T = 2$;  Booth $1$, buys no candy, not enough money;  Booth $2$, buys candy for $2$, $T = 0$. 

No candy can be bought later. The total number of candies bought is $10$.

In the second example he has $1$ burle left at the end of his path, no candy can be bought with this amount.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are n players numbered from 0 to n-1 with ranks. The i-th player has rank i.

Players can form teams: the team should consist of three players and no pair of players in the team should have a conflict. The rank of the team is calculated using the following algorithm: let i, j, k be the ranks of players in the team and i < j < k, then the rank of the team is equal to A ⋅ i + B ⋅ j + C ⋅ k.

You are given information about the pairs of players who have a conflict. Calculate the total sum of ranks over all possible valid teams modulo 2^{64}.

Input

The first line contains two space-separated integers n and m (3 ≤ n ≤ 2 ⋅ 10^5, 0 ≤ m ≤ 2 ⋅ 10^5) — the number of players and the number of conflicting pairs.

The second line contains three space-separated integers A, B and C (1 ≤ A, B, C ≤ 10^6) — coefficients for team rank calculation.

Each of the next m lines contains two space-separated integers u_i and v_i (0 ≤ u_i, v_i < n, u_i ≠ v_i) — pair of conflicting players.

It's guaranteed that each unordered pair of players appears in the input file no more than once.

Output

Print single integer — the total sum of ranks over all possible teams modulo 2^{64}.

Examples

Input

4 0
2 3 4


Output

64


Input

4 1
2 3 4
1 0


Output

38


Input

6 4
1 5 3
0 3
3 5
5 4
4 3


Output

164

Note

In the first example all 4 teams are valid, i.e. triples: {0, 1, 2}, {0, 1, 3}, {0, 2, 3} {1, 2, 3}.

In the second example teams are following: {0, 2, 3}, {1, 2, 3}.

In the third example teams are following: {0, 1, 2}, {0, 1, 4}, {0, 1, 5}, {0, 2, 4}, {0, 2, 5}, {1, 2, 3}, {1, 2, 4}, {1, 2, 5}.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Schedule

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
At the beginning of the new semester there is new schedule in the Berland State University. According to this schedule, *n* groups have lessons at the room 31. For each group the starting time of the lesson and the finishing time of the lesson are known. It has turned out that it is impossible to hold all lessons, because for some groups periods of their lessons intersect. If at some moment of time one groups finishes it's lesson, and the other group starts the lesson, their lessons don't intersect.

The dean wants to cancel the lesson in one group so that no two time periods of lessons of the remaining groups intersect. You are to find all ways to do that.

Input Specification:
The first line contains integer *n* (1<=≤<=*n*<=≤<=5000) — amount of groups, which have lessons in the room 31. Then *n* lines follow, each of them contains two integers *l**i* *r**i* (1<=≤<=*l**i*<=&lt;<=*r**i*<=≤<=106) — starting and finishing times of lesson of the *i*-th group. It is possible that initially no two lessons intersect (see sample 1).

Output Specification:
Output integer *k* — amount of ways to cancel the lesson in exactly one group so that no two time periods of lessons of the remaining groups intersect. In the second line output *k* numbers — indexes of groups, where it is possible to cancel the lesson. Groups are numbered starting from 1 in the order that they were given in the input. Output the numbers in increasing order.

Demo Input:
['3\n3 10\n20 30\n1 3\n', '4\n3 10\n20 30\n1 3\n1 39\n', '3\n1 5\n2 6\n3 7\n']

Demo Output:
['3\n1 2 3 ', '1\n4 ', '0\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Radewoosh is playing a computer game. There are n levels, numbered 1 through n. Levels are divided into k regions (groups). Each region contains some positive number of consecutive levels.

The game repeats the the following process:

  1. If all regions are beaten then the game ends immediately. Otherwise, the system finds the first region with at least one non-beaten level. Let X denote this region.
  2. The system creates an empty bag for tokens. Each token will represent one level and there may be many tokens representing the same level.
    * For each already beaten level i in the region X, the system adds ti tokens to the bag (tokens representing the i-th level). 
    * Let j denote the first non-beaten level in the region X. The system adds tj tokens to the bag. 
  3. Finally, the system takes a uniformly random token from the bag and a player starts the level represented by the token. A player spends one hour and beats the level, even if he has already beaten it in the past. 



Given n, k and values t1, t2, ..., tn, your task is to split levels into regions. Each level must belong to exactly one region, and each region must contain non-empty consecutive set of levels. What is the minimum possible expected number of hours required to finish the game?

Input

The first line of the input contains two integers n and k (1 ≤ n ≤ 200 000, 1 ≤ k ≤ min(50, n)) — the number of levels and the number of regions, respectively.

The second line contains n integers t1, t2, ..., tn (1 ≤ ti ≤ 100 000).

Output

Print one real number — the minimum possible expected value of the number of hours spent to finish the game if levels are distributed between regions in the optimal way. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 4.

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct if <image>.

Examples

Input

4 2
100 3 5 7


Output

5.7428571429


Input

6 2
1 2 4 8 16 32


Output

8.5000000000

Note

In the first sample, we are supposed to split 4 levels into 2 regions. It's optimal to create the first region with only one level (it must be the first level). Then, the second region must contain other three levels.

In the second sample, it's optimal to split levels into two regions with 3 levels each.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are n military men in the Berland army. Some of them have given orders to other military men by now. Given m pairs (xi, yi), meaning that the military man xi gave the i-th order to another military man yi.

It is time for reform! The Berland Ministry of Defence plans to introduce ranks in the Berland army. Each military man should be assigned a rank — integer number between 1 and k, inclusive. Some of them have been already assigned a rank, but the rest of them should get a rank soon.

Help the ministry to assign ranks to the rest of the army so that:

  * for each of m orders it is true that the rank of a person giving the order (military man xi) is strictly greater than the rank of a person receiving the order (military man yi); 
  * for each rank from 1 to k there is at least one military man with this rank. 

Input

The first line contains three integers n, m and k (1 ≤ n ≤ 2·105, 0 ≤ m ≤ 2·105, 1 ≤ k ≤ 2·105) — number of military men in the Berland army, number of orders and number of ranks.

The second line contains n integers r1, r2, ..., rn, where ri > 0 (in this case 1 ≤ ri ≤ k) means that the i-th military man has been already assigned the rank ri; ri = 0 means the i-th military man doesn't have a rank yet.

The following m lines contain orders one per line. Each order is described with a line containing two integers xi, yi (1 ≤ xi, yi ≤ n, xi ≠ yi). This line means that the i-th order was given by the military man xi to the military man yi. For each pair (x, y) of military men there could be several orders from x to y.

Output

Print n integers, where the i-th number is the rank of the i-th military man. If there are many solutions, print any of them.

If there is no solution, print the only number -1.

Examples

Input

5 3 3
0 3 0 0 2
2 4
3 4
3 5


Output

1 3 3 2 2 


Input

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


Output

2 4 5 4 1 3 5 


Input

2 2 2
2 1
1 2
2 1


Output

-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Our juniors has just entered in coding community. Their first task is to find the frequency of Best numbers present in given list of elements.
Best numbers are numbers which are divisible by 2.

SAMPLE INPUT
2
5
1 2 3 4 5
3
1 3 5

SAMPLE OUTPUT
2
0

Explanation

Number of test cases=2
1st test case, number of elements =5 
Best numbers are  2 , 4 ; frequency=2
2nd test case, number of elements =3
No Best numbers

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Aramic script

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
In Aramic language words can only represent objects.

Words in Aramic have special properties: 
 -  A word is a root if it does not contain the same letter more than once. -  A root and all its permutations represent the same object. -  The root $x$ of a word $y$ is the word that contains all letters that appear in $y$ in a way that each letter appears once. For example, the root of "aaaa", "aa", "aaa" is "a", the root of "aabb", "bab", "baabb", "ab" is "ab". -  Any word in Aramic represents the same object as its root. 
You have an ancient script in Aramic. What is the number of different objects mentioned in the script?

Input Specification:
The first line contains one integer $n$ ($1 \leq n \leq 10^3$) — the number of words in the script.

The second line contains $n$ words $s_1, s_2, \ldots, s_n$ — the script itself. The length of each string does not exceed $10^3$.

It is guaranteed that all characters of the strings are small latin letters.

Output Specification:
Output one integer — the number of different objects mentioned in the given ancient Aramic script.

Demo Input:
['5\na aa aaa ab abb\n', '3\namer arem mrea\n']

Demo Output:
['2', '1']

Note:
In the first test, there are two objects mentioned. The roots that represent them are "a","ab".

In the second test, there is only one object, its root is "amer", the other strings are just permutations of "amer".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chang's new maths teacher is very enthusiastic about making sure that students understand the concept rather than remembering it. On her first day at teaching, she gives an assignment to all the students to test their potential. Chang wants to demonstrate that he understands the concept rather than rote learning. Help Chang in doing this by solving the hardest problem in the assignment. The problem is written as follows. 

A perfect function is defined in the following manner.

- F(x, y) = x2 + y for 1 ≤ x ≤ A, 1 ≤ y ≤ B
- F(x, y) = 2 otherwise

Find the number of integral pairs (x, y) such that F(x, y) is a perfect square.

-----Input-----
First and the only line of the input contains two single space separated integers A and B.

-----Output-----
Output a single integer indicating the output to the only test case.

-----Constraints-----
- 1 ≤ A, B ≤ 106

-----Example-----
Input:
4 4

Output:
1

-----Explanation-----
Example case 1.
(1, 3) is the only pair such that x = 1, y = 3 satisfying x <= 4 and y <= 4. 1^2 + 3 = 4 which is a perfect square.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.