vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Masha's little brother draw two points on a sheet of paper. After that, he draws some circles and gave the sheet to his sister. 

Masha has just returned from geometry lesson so she instantly noticed some interesting facts about brother's drawing.

At first, the line going through two points, that brother drew, doesn't intersect or touch any circle.

Also, no two circles intersect or touch, and there is no pair of circles such that one circle is located inside another.

Moreover, for each circle, Masha drew a square of the minimal area with sides parallel axis such that this circle is located inside the square and noticed that there is no two squares intersect or touch and there is no pair of squares such that one square is located inside other.

Now Masha wants to draw circle of minimal possible radius such that it goes through two points that brother drew and doesn't intersect any other circle, but other circles can touch Masha's circle and can be located inside it.

It's guaranteed, that answer won't exceed 1012. It should be held for hacks as well.

Input

First line contains four integers x1, y1, x2, y2 ( - 105 ≤ x1, y1, x2, y2 ≤ 105) — coordinates of points that brother drew. First point has coordinates (x1, y1) and second point has coordinates (x2, y2). These two points are different.

The second line contains single integer n (1 ≤ n ≤ 105) — the number of circles that brother drew.

Next n lines contains descriptions of circles. Each line contains three integers xi, yi, ri ( - 105 ≤ xi, yi ≤ 105, 1 ≤ ri ≤ 105) describing circle with center (xi, yi) and radius ri.

Output

Output smallest real number, that it's possible to draw a circle with such radius through given points in such a way that it doesn't intersect other circles.

The output is considered correct if it has a relative or absolute error of at most 10 - 4.

Examples

Input

2 4 7 13
3
3 0 1
12 4 2
-4 14 2


Output

5.1478150705

Input

-2 3 10 -10
2
7 0 3
-5 -5 2


Output

9.1481831923

Note

<image> <image>

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
Petya has noticed that when he types using a keyboard, he often presses extra buttons and adds extra letters to the words. Of course, the spell-checking system underlines the words for him and he has to click every word and choose the right variant. Petya got fed up with correcting his mistakes himself, that’s why he decided to invent the function that will correct the words itself. Petya started from analyzing the case that happens to him most of the time, when all one needs is to delete one letter for the word to match a word from the dictionary. Thus, Petya faces one mini-task: he has a printed word and a word from the dictionary, and he should delete one letter from the first word to get the second one. And now the very non-trivial question that Petya faces is: which letter should he delete?

Input Specification:
The input data contains two strings, consisting of lower-case Latin letters. The length of each string is from 1 to 106 symbols inclusive, the first string contains exactly 1 symbol more than the second one.

Output Specification:
In the first line output the number of positions of the symbols in the first string, after the deleting of which the first string becomes identical to the second one. In the second line output space-separated positions of these symbols in increasing order. The positions are numbered starting from 1. If it is impossible to make the first string identical to the second string by deleting one symbol, output one number 0.

Demo Input:
['abdrakadabra\nabrakadabra\n', 'aa\na\n', 'competition\ncodeforces\n']

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Darshak (Dark)  likes to get fruits from trees a lot,he always like to eat those natural fruits directly from the tree.
Today he has an infinite full binary tree (each node has exactly two child's) with special properties.
Dark's tree has the following special properties :
Each node of the tree has a value of goodness.
The root of the tree is labelled as 1(value of goodness). For a node labelled v, it's left child is labelled as 2v(value of goodness)  and it's right child is labelled as 2v+1(value of goodness).
Dark wants to fulfill Q queries on this tree. 

Each query has two numbers 'x' and 'y'.He travels on the path from node 'x' to node 'y', on traversing each node has value of goodness if the value found to be a prime number  it would get subtracted while if it is composite number then it gets added.

Help Dark accomplishing this task.

Input:

First line of the input contains an integer Q denoting the number of queries. Next Q lines of the input contain Q queries (one per line) having 2 numbers 'x' and 'y'.

Output:

For each query print the value of goodness on entire traversal from node 'x' to node 'y'.

Constraints:

1 ≤ Q ≤ 5*10^3

1 ≤ x,y ≤ 5 * 10^6

Scoring :

subtask1 :

 1 ≤ x,y ≤ 10000        30 points

subtask2  :

1 ≤ x,y ≤ 5 * 10^6       70 points

Author : Darshak Mehta

SAMPLE INPUT
2
1 5
4 4

SAMPLE OUTPUT
-6
4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given string str of length N. The task is to find the minimum characters to be added at the front to make string palindrome.
Note: A palindrome is a word which reads the same backward as forward. Example: "madam".
Example 1:
Input:
S = "abc"
Output: 2
Explanation: 
Add 'b' and 'c' at front of above string to make it
palindrome : "cbabc"
Example 2:
Input:
S = "aacecaaa"
Output: 1
Explanation: Add 'a' at front of above string
to make it palindrome : "aaacecaaa"
Your Task:  
You don't need to read input or print anything. Your task is to complete the function minChar() which takes a string S and returns an integer as output.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 <= S.length <= 10^{6}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
While on summer camp, you are playing a game of hide-and-seek in the forest. You need to designate a “safe zone”, where, if the players manage to sneak there without being detected, they beat the seeker. It is therefore of utmost importance that this zone is well-chosen.

You point towards a tree as a suggestion, but your fellow hide-and-seekers are not satisfied. After all, the tree has branches stretching far and wide, and it will be difficult to determine whether a player has reached the safe zone. They want a very specific demarcation for the safe zone. So, you tell them to go and find some sticks, of which you will use three to mark a non-degenerate triangle (i.e. with strictly positive area) next to the tree which will count as the safe zone. After a while they return with a variety of sticks, but you are unsure whether you can actually form a triangle with the available sticks.

Can you write a program that determines whether you can make a triangle with exactly three of the collected sticks?

-----Input-----
The first line contains a single integer $N$, with $3 \leq N \leq 20000$, the number of sticks collected. Then follows one line with $N$ positive integers, each less than $2^{60}$, the lengths of the sticks which your fellow campers have collected.

-----Output-----
Output a single line containing a single word: possible if you can make a non-degenerate triangle with three sticks of the provided lengths, and impossible if you can not.

-----Examples-----
Sample Input:
3
1 1 1
Sample Output:
possible

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array nums of non-negative integers. nums is considered special if there exists a number x such that there are exactly x numbers in nums that are greater than or equal to x.
Notice that x does not have to be an element in nums.
Return x if the array is special, otherwise, return -1. It can be proven that if nums is special, the value for x is unique.
 
Example 1:
Input: nums = [3,5]
Output: 2
Explanation: There are 2 values (3 and 5) that are greater than or equal to 2.

Example 2:
Input: nums = [0,0]
Output: -1
Explanation: No numbers fit the criteria for x.
If x = 0, there should be 0 numbers >= x, but there are 2.
If x = 1, there should be 1 number >= x, but there are 0.
If x = 2, there should be 2 numbers >= x, but there are 0.
x cannot be greater since there are only 2 numbers in nums.

Example 3:
Input: nums = [0,4,3,0,4]
Output: 3
Explanation: There are 3 values that are greater than or equal to 3.

Example 4:
Input: nums = [3,6,7,7,0]
Output: -1

 
Constraints:

1 <= nums.length <= 100
0 <= nums[i] <= 1000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Iahub wants to enhance his multitasking abilities. In order to do this, he wants to sort n arrays simultaneously, each array consisting of m integers.

Iahub can choose a pair of distinct indices i and j (1 ≤ i, j ≤ m, i ≠ j). Then in each array the values at positions i and j are swapped only if the value at position i is strictly greater than the value at position j.

Iahub wants to find an array of pairs of distinct indices that, chosen in order, sort all of the n arrays in ascending or descending order (the particular order is given in input). The size of the array can be at most <image> (at most <image> pairs). Help Iahub, find any suitable array.

Input

The first line contains three integers n (1 ≤ n ≤ 1000), m (1 ≤ m ≤ 100) and k. Integer k is 0 if the arrays must be sorted in ascending order, and 1 if the arrays must be sorted in descending order. Each line i of the next n lines contains m integers separated by a space, representing the i-th array. For each element x of the array i, 1 ≤ x ≤ 106 holds.

Output

On the first line of the output print an integer p, the size of the array (p can be at most <image>). Each of the next p lines must contain two distinct integers i and j (1 ≤ i, j ≤ m, i ≠ j), representing the chosen indices.

If there are multiple correct answers, you can print any.

Examples

Input

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


Output

3
2 4
2 3
4 5


Input

3 2 1
1 2
2 3
3 4


Output

1
2 1

Note

Consider the first sample. After the first operation, the arrays become [1, 3, 2, 5, 4] and [1, 2, 3, 4, 5]. After the second operation, the arrays become [1, 2, 3, 5, 4] and [1, 2, 3, 4, 5]. After the third operation they become [1, 2, 3, 4, 5] and [1, 2, 3, 4, 5].

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Petya loves football very much, especially when his parents aren't home. Each morning he comes to the yard, gathers his friends and they play all day. From time to time they have a break to have some food or do some chores (for example, water the flowers).

The key in football is to divide into teams fairly before the game begins. There are n boys playing football in the yard (including Petya), each boy's football playing skill is expressed with a non-negative characteristic ai (the larger it is, the better the boy plays). 

Let's denote the number of players in the first team as x, the number of players in the second team as y, the individual numbers of boys who play for the first team as pi and the individual numbers of boys who play for the second team as qi. Division n boys into two teams is considered fair if three conditions are fulfilled:

  * Each boy plays for exactly one team (x + y = n). 
  * The sizes of teams differ in no more than one (|x - y| ≤ 1). 
  * The total football playing skills for two teams differ in no more than by the value of skill the best player in the yard has. More formally: <image>



Your task is to help guys divide into two teams fairly. It is guaranteed that a fair division into two teams always exists.

Input

The first line contains the only integer n (2 ≤ n ≤ 105) which represents the number of guys in the yard. The next line contains n positive space-separated integers, ai (1 ≤ ai ≤ 104), the i-th number represents the i-th boy's playing skills. 

Output

On the first line print an integer x — the number of boys playing for the first team. On the second line print x integers — the individual numbers of boys playing for the first team. On the third line print an integer y — the number of boys playing for the second team, on the fourth line print y integers — the individual numbers of boys playing for the second team. Don't forget that you should fulfil all three conditions: x + y = n, |x - y| ≤ 1, and the condition that limits the total skills.

If there are multiple ways to solve the problem, print any of them.

The boys are numbered starting from one in the order in which their skills are given in the input data. You are allowed to print individual numbers of boys who belong to the same team in any order.

Examples

Input

3
1 2 1


Output

2
1 2 
1
3 


Input

5
2 3 3 1 1


Output

3
4 1 3 
2
5 2 

Note

Let's consider the first sample test. There we send the first and the second boy to the first team and the third boy to the second team. Let's check all three conditions of a fair division. The first limitation is fulfilled (all boys play), the second limitation on the sizes of groups (|2 - 1| = 1 ≤ 1) is fulfilled, the third limitation on the difference in skills ((2 + 1) - (1) = 2 ≤ 2) is fulfilled.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let's denote a function $f(x)$ in such a way: we add $1$ to $x$, then, while there is at least one trailing zero in the resulting number, we remove that zero. For example,   $f(599) = 6$: $599 + 1 = 600 \rightarrow 60 \rightarrow 6$;  $f(7) = 8$: $7 + 1 = 8$;  $f(9) = 1$: $9 + 1 = 10 \rightarrow 1$;  $f(10099) = 101$: $10099 + 1 = 10100 \rightarrow 1010 \rightarrow 101$. 

We say that some number $y$ is reachable from $x$ if we can apply function $f$ to $x$ some (possibly zero) times so that we get $y$ as a result. For example, $102$ is reachable from $10098$ because $f(f(f(10098))) = f(f(10099)) = f(101) = 102$; and any number is reachable from itself.

You are given a number $n$; your task is to count how many different numbers are reachable from $n$.


-----Input-----

The first line contains one integer $n$ ($1 \le n \le 10^9$).


-----Output-----

Print one integer: the number of different numbers that are reachable from $n$.


-----Examples-----
Input
1098

Output
20

Input
10

Output
19



-----Note-----

The numbers that are reachable from $1098$ are:

$1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18, 19, 1098, 1099$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Some numbers have funny properties. For example:

> 89 --> 8¹ + 9² = 89 * 1

> 695 --> 6² + 9³ + 5⁴= 1390 = 695 * 2

> 46288 --> 4³ + 6⁴+ 2⁵ + 8⁶ + 8⁷ = 2360688 = 46288 * 51

Given a positive integer n written as abcd... (a, b, c, d... being digits) and a positive integer p 
- we want to find a positive integer k, if it exists, such as the sum of the digits of n taken to the successive powers of p is equal to k * n. 

In other words:

> Is there an integer k such as : (a ^ p + b ^ (p+1) + c ^(p+2) + d ^ (p+3) + ...) = n * k

If it is the case we will return k, if not return -1.

**Note**: n and p will always be given as strictly positive integers.

```python
dig_pow(89, 1) should return 1 since 8¹ + 9² = 89 = 89 * 1
dig_pow(92, 1) should return -1 since there is no k such as 9¹ + 2² equals 92 * k
dig_pow(695, 2) should return 2 since 6² + 9³ + 5⁴= 1390 = 695 * 2
dig_pow(46288, 3) should return 51 since 4³ + 6⁴+ 2⁵ + 8⁶ + 8⁷ = 2360688 = 46288 * 51
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given is a string S representing the day of the week today.
S is SUN, MON, TUE, WED, THU, FRI, or SAT, for Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, and Saturday, respectively.
After how many days is the next Sunday (tomorrow or later)?

-----Constraints-----
 - S is SUN, MON, TUE, WED, THU, FRI, or SAT.

-----Input-----
Input is given from Standard Input in the following format:
S

-----Output-----
Print the number of days before the next Sunday.

-----Sample Input-----
SAT

-----Sample Output-----
1

It is Saturday today, and tomorrow will be Sunday.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have records of employee name as string (E_{name}) and salary as positive integer (S). You have to sort the records on the basis of employee salary, if salary is same then use employee name for comparison.
Example 1:
Input: N = 2
arr[] = {{xbnnskd, 100}, {geek, 50}}
Output: {geek 50}, {xbnnskd 100}
Explanation: geek has lowest salary 
as 50 and xbnnskd has more salary.
Example 2: 
Input: N = 2
arr[] = {{shyam, 50}, {ram, 50}} 
Output: ram 50 shyam 50
Your Task:
This is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function sortRecords() that takes array arr[] and integer N as parameters and sort the array according to the above-given conditions. The function does not return anything.
 
Expected Time Complexity: O(NlogN).
Expected Auxiliary Space: O(1).
 
Constraints:
1 ≤ N ≤ 10^{3}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
While some people enjoy spending their time solving programming contests, Dina prefers taking beautiful pictures. As soon as Byteland Botanical Garden announced Summer Oenothera Exhibition she decided to test her new camera there.

The exhibition consists of l = 10^{100} Oenothera species arranged in a row and consecutively numbered with integers from 0 to l - 1. Camera lens allows to take a photo of w species on it, i.e. Dina can take a photo containing flowers with indices from x to x + w - 1 for some integer x between 0 and l - w. We will denote such photo with [x, x + w - 1].

She has taken n photos, the i-th of which (in chronological order) is [x_i, x_i + w - 1] in our notation. She decided to build a time-lapse video from these photos once she discovered that Oenothera blossoms open in the evening. 

Dina takes each photo and truncates it, leaving its segment containing exactly k flowers, then she composes a video of these photos keeping their original order and voilà, a beautiful artwork has been created!

A scene is a contiguous sequence of photos such that the set of flowers on them is the same. The change between two scenes is called a cut. For example, consider the first photo contains flowers [1, 5], the second photo contains flowers [3, 7] and the third photo contains flowers [8, 12]. If k = 3, then Dina can truncate the first and the second photo into [3, 5], and the third photo into [9, 11]. First two photos form a scene, third photo also forms a scene and the transition between these two scenes which happens between the second and the third photos is a cut. If k = 4, then each of the transitions between photos has to be a cut.

Dina wants the number of cuts to be as small as possible. Please help her! Calculate the minimum possible number of cuts for different values of k.

Input

The first line contains three positive integer n, w, q (1 ≤ n, q ≤ 100 000, 1 ≤ w ≤ 10^9) — the number of taken photos, the number of flowers on a single photo and the number of queries.

Next line contains n non-negative integers x_i (0 ≤ x_i ≤ 10^9) — the indices of the leftmost flowers on each of the photos.

Next line contains q positive integers k_i (1 ≤ k_i ≤ w) — the values of k for which you have to solve the problem.

It's guaranteed that all k_i are distinct.

Output

Print q integers — for each width of the truncated photo k_i, the minimum number of cuts that is possible.

Examples

Input

3 6 5
2 4 0
1 2 3 4 5


Output

0
0
1
1
2


Input

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


Output

0
1
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef has opened up a new restaurant. Like every other restaurant, critics critique this place. The Chef wants to gather as much positive publicity as he can. Also, he is very aware of the fact that people generally do not tend to go through all the reviews. So he picks out the positive reviews and posts it on the website of the restaurant. A review is represented by an integer which is the overall rating of the restaurant as calculated by that particular review.
A review is considered to be positive if it is among the top one-third of the total reviews when they are sorted by their rating. For example, suppose the ratings given by 8 different reviews are as follows:

2 8 3 1 6 4 5 7

Then the top one-third reviews will be 8 and 7. Note that we considered one-third to be 8/3=2 top reviews according to integer division. (see Notes)
So here is what the Chef wants from you: Given the reviews(ratings) by different critics, the Chef needs you to tell him what is the minimum rating that his website will be displaying. For example in the above case, the minimum rating that will be displayed is 7. Also, different critics keep reviewing the restaurant continuosly. So the new reviews keep coming in. The Chef wants your website ratings to be up-to-date. So you should keep updating the ratings there. At any point of time, the Chef might want to know the minimum rating being displayed. You'll have to answer that query. An interesting thing to note here is that a review might be in the website for some time and get knocked out later because of new better reviews and vice-versa.
Notes: To be precise, the number of reviews displayed website will be floor(n / 3), where n denotes the current number of all reviews.

------ Input ------ 

First line of the input file consists of a single integer N, the number of operations to follow. The next N lines contain one operation each on a single line. An operation can be of 2 types:

1 x : Add a review with rating 'x' to the exisiting list of reviews (x is an integer)

2 : Report the current minimum rating on the website 

------ Output ------ 

For every test case, output a single integer each for every operation of type 2 mentioned above. If no review qualifies as a positive review, print "No reviews yet".

------ Constraints ------ 

1 ≤ N ≤ 250000
1 ≤ x ≤ 1000000000

----- Sample Input 1 ------ 
10
1 1
1 7
2
1 9
1 21
1 8
1 5
2
1 9
2
----- Sample Output 1 ------ 
No reviews yet
9
9
----- explanation 1 ------ 
Before the first query of the Chef, i.e. the first operation of type 2 in the input, the only ratings were 1 & 7. Thus, there will be total of 2/3 = 0 positive ratings. For the next two, the ratings list now looks like: 1 5 7 8 9 21. Hence, top one-third will have 6/3 = 2 ratings as positive. And lowest displayed rating will be 9. Similarly for the last operation of type 2. Note that there are two ratings of the same value 9 now and only one of them can be in the top reviews. In such a case, you can choose any one of them.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given time in 24-hour format, convert it to words. 

```
For example:
13:00 = one o'clock 
13:09 = nine minutes past one 
13:15 = quarter past one 
13:29 = twenty nine minutes past one
13:30 = half past one 
13:31 = twenty nine minutes to two
13:45 = quarter to two 
00:48 = twelve minutes to one
00:08 = eight minutes past midnight
12:00 = twelve o'clock
00:00 = midnight

Note: If minutes == 0, use 'o'clock'. If minutes <= 30, use 'past', and for minutes > 30, use 'to'. 

```

More examples in test cases. Good luck!

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