vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
You are given a list L with n items. Find the number of ways to split this list into two disjoint non-empty groups with equal XOR value between their items.

A disjoint group means that each item of a  list L is located in exactly one group. 

The answer can be very large, so print it by modulo (10^9+7).

Input
First line of input contains one integer n which denotes  the size of list L. 

Second line contains n space separated integers enter code hereL1,L2,…,Ln, representing items in the list L.

Output
In each line corresponding to input print one integer (i.e., answer) - number of ways for splitting the list into two groups with equal XOR by modulo 10^9+7.

Constraints
1 ≤ n ≤ 10^5

0 ≤ Li ≤ 10^9

SAMPLE INPUT
3
4 0 4

SAMPLE OUTPUT
3

Explanation

We have list L with three elements L = {4,0,4}. 

We can split this list in the following three ways: 
{4,0},{4}. The XOR of the first group is equal to 4 (4 XOR 0 = 4). The XOR of the second group is equal to 4 and so XOR of 4 and 4 is 0.
{4,4},{0}. The XOR of the first group is equal to 0 (4 XOR 4 = 0). The XOR of the second group is equal to 0.
{0,4},{4} same as 1.

We have two fours, so we have 2 possible groups  of {0,4}.

Therefore the Answer is 3.

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

The first line contains a single integer n (1 ≤ n ≤ 1000) — the number of points on a plane.

Each of the next n lines contains two real coordinates xi and yi of the <image> point, specified with exactly 2 fractional digits. All coordinates are between  - 1000 and 1000, inclusive.

Output

Output a single real number θ — the answer to the problem statement. The absolute or relative error of your answer should be at most 10 - 2.

Examples

Input

8
-2.14 2.06
-1.14 2.04
-2.16 1.46
-2.14 0.70
-1.42 0.40
-0.94 -0.48
-1.42 -1.28
-2.16 -1.62


Output

5.410


Input

5
2.26 1.44
2.28 0.64
2.30 -0.30
1.58 0.66
3.24 0.66


Output

5.620


Input

8
6.98 2.06
6.40 1.12
5.98 0.24
5.54 -0.60
7.16 0.30
7.82 1.24
8.34 0.24
8.74 -0.76


Output

5.480


Input

5
10.44 2.06
10.90 0.80
11.48 -0.48
12.06 0.76
12.54 2.06


Output

6.040


Input

8
16.94 2.42
15.72 2.38
14.82 1.58
14.88 0.50
15.76 -0.16
16.86 -0.20
17.00 0.88
16.40 0.92


Output

6.040


Input

7
20.62 3.00
21.06 2.28
21.56 1.36
21.66 0.56
21.64 -0.52
22.14 2.32
22.62 3.04


Output

6.720

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: April Fools' Problem (easy)

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The marmots have prepared a very easy problem for this year's HC2 – this one. It involves numbers *n*, *k* and a sequence of *n* positive integers *a*1,<=*a*2,<=...,<=*a**n*. They also came up with a beautiful and riveting story for the problem statement. It explains what the input means, what the program should output, and it also reads like a good criminal.

However I, Heidi, will have none of that. As my joke for today, I am removing the story from the statement and replacing it with these two unhelpful paragraphs. Now solve the problem, fools!

Input Specification:
The first line of the input contains two space-separated integers *n* and *k* (1<=≤<=*k*<=≤<=*n*<=≤<=2200). The second line contains *n* space-separated integers *a*1,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=104).

Output Specification:
Output one number.

Demo Input:
['8 5\n1 1 1 1 1 1 1 1\n', '10 3\n16 8 2 4 512 256 32 128 64 1\n', '5 1\n20 10 50 30 46\n', '6 6\n6 6 6 6 6 6\n', '1 1\n100\n']

Demo Output:
['5', '7', '10', '36', '100']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Read problems statements in Mandarin Chinese  and Russian. 

Sereja have array A' that contain N integers. Now Sereja want to permute elements of the array, he want to use some permutation p, such that A[i] = A'[p[i]], where A - new array. 
 
Lets function f(A,i) = S - A[i] - A[i +1] - ... - A[j], where j is the maximum possible index, such that A[i] + A[i + 1] + ... + A[j] ≤ S, if A[i] > S, f(A, i) = S.
 
Help Sereja to find such permutation p, such that (f(A, 1) + f(A, 2) + ... f(A, k))/k will be as low as possible. 

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

First line of input contain integer T - number of testcases. Next lines contain T testcases. First line of each testcase contain three integers N, k, S. Next line contain N integers - array A'.
 
------ Output ------ 

For each testcase output N numbers in one line - permutation p. 
 
------ Constraints ------ 

$1 ≤ T ≤ 10$
$1 ≤ N ≤ 2000$
$1 ≤ k ≤ N$
$1 ≤ A'[i] ≤ 10^{4}$
$1 ≤ S ≤ 10^{9}$

------ Example ------ 

Input:
2
3 2 4
3 4 1
4 4 1
1 1 1 1

Output:
2 1 3
4 3 2 1

------ Scoring ------ 

Suppose Sum will be sum of yours (f(A, 1) + f(A, 2) + ... f(A, k))/k per each testcase.  
Lets B will be the smallest such sum. Your score will be equal to B/Sum. Lower scores will earn more points.

We have 20 official test files. You must correctly solve all test files to receive OK. During the contest, your overall score is the sum of the scores on the first 4 test files. After the contest, all solutions will be rescored by the sum of the scores on the rest 16 test files. Note, that public part of the tests may not contain some border cases.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider the following numbers (where `n!` is `factorial(n)`):
```
u1 = (1 / 1!) * (1!)
u2 = (1 / 2!) * (1! + 2!)
u3 = (1 / 3!) * (1! + 2! + 3!)
...
un = (1 / n!) * (1! + 2! + 3! + ... + n!)
```

Which will win: `1 / n!` or `(1! + 2! + 3! + ... + n!)`?

Are these numbers going to `0` because of `1/n!` or to infinity due
to the sum of factorials or to another number?

## Task
Calculate `(1 / n!) * (1! + 2! + 3! + ... + n!)` 
for a given `n`, where `n` is an integer greater or equal to `1`.

To avoid discussions about rounding, return the result **truncated** to 6 decimal places, for example:
```
1.0000989217538616 will be truncated to 1.000098
1.2125000000000001 will be truncated to 1.2125
```

## Remark
Keep in mind that factorials grow rather rapidly, and you need to handle large inputs.

## Hint
You could try to simplify the expression.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Puchi hates to carry luggage, but unfortunately he got a job to carry the luggage of his N friends in office. Each day,  one of his N friends, gives him the luggage of a particular weight to carry. You will be given the weight of luggage of each friend in the array Weight, where Weighti is the weight of luggage of i^th friend carried by Puchi on i^th day. It is given that all the luggages carried by Puchi are distinct in their weights. 
As Prateek assigned this job to Puchi, so for each day, he wants to know the number of days in future when Puchi will have to carry the luggage , having  weight less than the weight of luggage of current day.
Please help Prateek for the same.

Input:
The first line contains a single integer T, denoting the number of test cases. In each test case, the following input will be present: 
First line contains an integer N, where N represents the number of friends.
Next N line contains N integers, where i^th line contains i^th integer, which represents Weighti.   

Output:
Output exactly T lines. Each line contains N integer separated by a space, where i^th integer represents the number of luggage of future, which are less than the weight of luggage of the current day.

Constraints:

Subtask 1:
1 ≤ T ≤ 30
1 ≤ N ≤ 10^4
1 ≤ Weighti ≤ 10^6 
Subtask 2:
1 ≤ T ≤ 10
1 ≤ N ≤ 10^5
1 ≤ Weighti ≤ 10^6

SAMPLE INPUT
1
4
2
1
4
3

SAMPLE OUTPUT
1 0 1 0

Explanation

In sample input, given T =1 in first line and N = 4 in next line. In next 4 lines, Weighti i.e weight of luggage of each friend on i^th day is given.

For weight on first day i.e 2 ,future weights smaller than 2 are   {1} . Therefore output for this weight will be 1.
For weight on second day i.e 1, no future weights are smaller than 1. So output for this weight will be 0.
For weight on third day i.e 4, future weights smaller than  4 are {3}. So output for this weight will be 1.
For weight on fourth day i.e 3, no future weights are smaller than 3. So output for this weight will be 0.
So the final output is {1, 0, 1, 0}.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef received a permutation $P_1, P_2, \ldots, P_N$ and also an integer $D$ from his good friend Grux, because Grux was afraid he would forget them somewhere. However, since Grux was just playing with the permutation, it was all shuffled, and Chef only likes sorted permutations, so he decided to sort it by performing some swaps.
Chef wants to use the integer $D$ he just received, so he is only willing to swap two elements of the permutation whenever their absolute difference is exactly $D$. He has limited time, so you should determine the minimum number of swaps he needs to perform to sort the permutation, or tell him that it is impossible to sort it his way.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains two space-separated integers $N$ and $D$.
- The second line contains $N$ space-separated integers $P_1, P_2, \ldots, P_N$.

-----Output-----
For each test case, print a single line containing one integer ― the minimum number of swaps, or $-1$ if it is impossible to sort the permutation.

-----Constraints-----
- $1 \le T \le 20$
- $1 \le N \le 200,000$
- $1 \le D \le N$
- $1 \le P_i \le N$ for each valid $i$
- $P_1, P_2, \ldots, P_N$ are pairwise distinct
- the sum of $N$ over all test cases does not exceed $10^6$

-----Subtasks-----
Subtask #1 (20 points): $D = 1$
Subtask #2 (30 points):
- $N \le 1,000$
- the sum of $N$ over all test cases does not exceed $10,000$
Subtask #3 (50 points): original constraints

-----Example Input-----
2
5 2   
3 4 5 2 1
5 2    
4 3 2 1 5  

-----Example Output-----
3
-1

-----Explanation-----
Example case 1: Chef can perform the following swaps in this order:
- swap the first and fifth element
- swap the third and fifth element
- swap the second and fourth element

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an undirected graph G. G has N vertices and M edges. The vertices are numbered from 1 through N, and the i-th edge (1 ≤ i ≤ M) connects Vertex a_i and b_i. G does not have self-loops and multiple edges.

You can repeatedly perform the operation of adding an edge between two vertices. However, G must not have self-loops or multiple edges as the result. Also, if Vertex 1 and 2 are connected directly or indirectly by edges, your body will be exposed to a voltage of 1000000007 volts. This must also be avoided.

Under these conditions, at most how many edges can you add? Note that Vertex 1 and 2 are never connected directly or indirectly in the beginning.

Constraints

* 2 ≤ N ≤ 10^5
* 0 ≤ M ≤ 10^5
* 1 ≤ a_i < b_i ≤ N
* All pairs (a_i, b_i) are distinct.
* Vertex 1 and 2 in G are not connected directly or indirectly by edges.

Input

Input is given from Standard Input in the following format:


N M
a_1 b_1
:
a_M b_M


Output

Print the maximum number of edges that can be added.

Examples

Input

4 1
1 3


Output

2


Input

2 0


Output

0


Input

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


Output

12

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given are three integers N, K, and S.

Find a sequence A_1, A_2, ..., A_N of N integers between 1 and 10^9 (inclusive) that satisfies the condition below. We can prove that, under the conditions in Constraints, such a sequence always exists.

* There are exactly K pairs (l, r) of integers such that 1 \leq l \leq r \leq N and A_l + A_{l + 1} + \cdots + A_r = S.

Constraints

* 1 \leq N \leq 10^5
* 0 \leq K \leq N
* 1 \leq S \leq 10^9
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N K S


Output

Print a sequence satisfying the condition, in the following format:


A_1 A_2 ... A_N

Output

Print a sequence satisfying the condition, in the following format:


A_1 A_2 ... A_N

Examples

Input

4 2 3


Output

1 2 3 4


Input

5 3 100


Output

50 50 50 30 70

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Tom the Straight Builder has finally finished building his Great Wall. Being a Straight Builder he has of course built a wall with no bends in it at all. And as far as you can see he has built this wall infinitely long and infinitely thin.

On one side of the wall Tom’s wife Ellen has decided she wants to make a perfect lawn. It is not very important to Ellen (or to Tom for that matter) what shape it has or exactly where it is located, but Ellen requires the lawn to be at least $L$ square meters.

To guard this pristine lawn from annoying trespassers Ellen has brought her dog William. William is a vicious dog and will attack any human being except Ellen upon sight. William can not cross the wall in any way. To reduce his own mutilations Tom has decided to tie William up with a chain to a pole and minimize the area he can cover while still being able to cover the whole lawn. The pole has been placed at location $(0,0)$ and Tom is not able to move it (it is after all the center of the universe).

Tom needs to know what length of dog chain he needs to buy in the hardware store. Specifically he wants to know the shortest length chain in whole meters he can buy so that the dog is able to cover an area of at least $L$ square meters.

-----Input-----
The first line has one integer $L$ indicating the number of square meters for Ellen’s lawn. The second line contains two integers $x_1$ and $y_1$, followed by a third line containing two integers $x_2$ and $y_2$. These indicate that the wall passes through the points $(x_1, y_1)$ and $(x_2,y_2)$.

-----Output-----
Output the chain length, in whole meters, which Tom needs to acquire.

-----Limits-----
 - $1 \leq L \leq 10000$
 - $-10000 \leq x_1, y_1, x_2, y_2 \leq 10000$
 - $(x_1,y_1) \not= (x_2,y_2)$

-----Examples-----
Sample Input:
4
-10 0
-10 10
Sample Output:
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# Task
 If string has more than one neighboring dashes(e.g. --) replace they with one dash(-). 
 
 Dashes are considered neighbors even if there is some whitespace **between** them.

# Example

 For `str = "we-are- - - code----warriors.-"`
 
 The result should be `"we-are- code-warriors.-"`
 
# Input/Output


 - `[input]` string `str`
 
 
 - `[output]` a string

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are $n$ points on the plane, the $i$-th of which is at $(x_i, y_i)$. Tokitsukaze wants to draw a strange rectangular area and pick all the points in the area.

The strange area is enclosed by three lines, $x = l$, $y = a$ and $x = r$, as its left side, its bottom side and its right side respectively, where $l$, $r$ and $a$ can be any real numbers satisfying that $l < r$. The upper side of the area is boundless, which you can regard as a line parallel to the $x$-axis at infinity. The following figure shows a strange rectangular area. [Image] 

A point $(x_i, y_i)$ is in the strange rectangular area if and only if $l < x_i < r$ and $y_i > a$. For example, in the above figure, $p_1$ is in the area while $p_2$ is not.

Tokitsukaze wants to know how many different non-empty sets she can obtain by picking all the points in a strange rectangular area, where we think two sets are different if there exists at least one point in one set of them but not in the other.


-----Input-----

The first line contains a single integer $n$ ($1 \leq n \leq 2 \times 10^5$) — the number of points on the plane.

The $i$-th of the next $n$ lines contains two integers $x_i$, $y_i$ ($1 \leq x_i, y_i \leq 10^9$) — the coordinates of the $i$-th point.

All points are distinct.


-----Output-----

Print a single integer — the number of different non-empty sets of points she can obtain.


-----Examples-----
Input
3
1 1
1 2
1 3

Output
3

Input
3
1 1
2 1
3 1

Output
6

Input
4
2 1
2 2
3 1
3 2

Output
6



-----Note-----

For the first example, there is exactly one set having $k$ points for $k = 1, 2, 3$, so the total number is $3$.

For the second example, the numbers of sets having $k$ points for $k = 1, 2, 3$ are $3$, $2$, $1$ respectively, and their sum is $6$.

For the third example, as the following figure shows, there are  $2$ sets having one point;  $3$ sets having two points;  $1$ set having four points. 

Therefore, the number of different non-empty sets in this example is $2 + 3 + 0 + 1 = 6$. [Image]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a list of elements  of size N ( index starts from 1), each element is "a[k]"  , k ranges from 1 to N. You have to perform C number of operations on them .  An operation is either Update(U) or Query(Q). Update operations have syntax "U i j" , it means the  "ith" element a[i] of the list has to be replaced with the value "j"  . Query operations have syntax "Q i j" , it means you have to find out the maximum element in the range "i" to "j" both inclusive.
You have to print all the outputs of the queries "Q i j" in each line.

Input Format:
First line consist of N, the size of the number of elements. Second  line  consists of N elements separated by a space.
Next line consists of the number of queries C to be performed.
Next C lines consists of queries of the form: "U i j" or "Q i j".

Output Format:
Output  for  all the queries of the form "Q i j" separated by a line.

Constraints:
Elements of list can be fitted in a 4 byte integer   a[i] ≥0

1 ≤ N ≤ 1000000

1 ≤ C ≤ 1000000

1 ≤ i <  j ≤N

SAMPLE INPUT
10
4 1 0 4 5 5 0 2 2 6 
5
Q 1 8
Q 3 9
U 6 10
U 1 6
Q 4 6

SAMPLE OUTPUT
5
5
10

Explanation

Given list is 1-based index as mentioned in problem statement, for the first query "Q 1 8"  we have to find the maximum element from the range 1 to 8 both inclusive, answer is 5 as it can be seen in the list.

3rd query "U 6 10"  modifies the 6th element to 10.
5th query  "Q 4 6" ,finds the maximum element from the index 4 to 6 both inclusive and 10 is the right answer

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarp wants to buy exactly $n$ shovels. The shop sells packages with shovels. The store has $k$ types of packages: the package of the $i$-th type consists of exactly $i$ shovels ($1 \le i \le k$). The store has an infinite number of packages of each type.

Polycarp wants to choose one type of packages and then buy several (one or more) packages of this type. What is the smallest number of packages Polycarp will have to buy to get exactly $n$ shovels?

For example, if $n=8$ and $k=7$, then Polycarp will buy $2$ packages of $4$ shovels.

Help Polycarp find the minimum number of packages that he needs to buy, given that he:   will buy exactly $n$ shovels in total;  the sizes of all packages he will buy are all the same and the number of shovels in each package is an integer from $1$ to $k$, inclusive. 


-----Input-----

The first line contains an integer $t$ ($1 \le t \le 100$) — the number of test cases in the input. Then, $t$ test cases follow, one per line.

Each test case consists of two positive integers $n$ ($1 \le n \le 10^9$) and $k$ ($1 \le k \le 10^9$) — the number of shovels and the number of types of packages.


-----Output-----

Print $t$ answers to the test cases. Each answer is a positive integer — the minimum number of packages.


-----Example-----
Input
5
8 7
8 1
6 10
999999733 999999732
999999733 999999733

Output
2
8
1
999999733
1



-----Note-----

The answer to the first test case was explained in the statement.

In the second test case, there is only one way to buy $8$ shovels — $8$ packages of one shovel.

In the third test case, you need to buy a $1$ package of $6$ shovels.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasya owns three big integers — $a, l, r$. Let's define a partition of $x$ such a sequence of strings $s_1, s_2, \dots, s_k$ that $s_1 + s_2 + \dots + s_k = x$, where $+$ is a concatanation of strings. $s_i$ is the $i$-th element of the partition. For example, number $12345$ has the following partitions: ["1", "2", "3", "4", "5"], ["123", "4", "5"], ["1", "2345"], ["12345"] and lots of others.

Let's call some partition of $a$ beautiful if each of its elements contains no leading zeros.

Vasya want to know the number of beautiful partitions of number $a$, which has each of $s_i$ satisfy the condition $l \le s_i \le r$. Note that the comparison is the integer comparison, not the string one.

Help Vasya to count the amount of partitions of number $a$ such that they match all the given requirements. The result can be rather big, so print it modulo $998244353$.


-----Input-----

The first line contains a single integer $a~(1 \le a \le 10^{1000000})$.

The second line contains a single integer $l~(0 \le l \le 10^{1000000})$.

The third line contains a single integer $r~(0 \le r \le 10^{1000000})$.

It is guaranteed that $l \le r$.

It is also guaranteed that numbers $a, l, r$ contain no leading zeros.


-----Output-----

Print a single integer — the amount of partitions of number $a$ such that they match all the given requirements modulo $998244353$.


-----Examples-----
Input
135
1
15

Output
2

Input
10000
0
9

Output
1



-----Note-----

In the first test case, there are two good partitions $13+5$ and $1+3+5$.

In the second test case, there is one good partition $1+0+0+0+0$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You and your friends have gathered at your house to prepare for the Big Game, which you all plan to attend in the afternoon at the football stadium across town. The problem: you only have $k$ cars between you, with each car seating five people (including the driver), so you might have to take multiple trips to get all $n$ people to the stadium. In addition, some of your friends know the city better than others, and so take different amounts of time to drive to the stadium from your house. You’d like to procrastinate as long as possible before hitting the road: can you concoct a transportation plan that gets all people to the stadium in the shortest amount of time possible?

More specifically, each person $i$ currently at your house can drive to the stadium in $t_ i$ minutes. All $k$ cars are currently parked at your house. Any person can drive any car (so the cars are interchangeable). After a car arrives at the stadium, any person currently at the stadium can immediately start driving back to your house (and it takes person $i$ the same amount of time $t_ i$ to drive back as to drive to the stadium), or alternatively, cars can be temporarily or permanently parked at the stadium. Drivers driving to the stadium can take up to four passengers with them, but drivers driving back can NOT take any passenger. You care only about getting all $n$ people from your house to the stadium—you do NOT need to park all $k$ cars at the stadium, if doing so would require more time than an alternative plan that leaves some cars at your house.

-----Input-----
The first line of input contains two space-separated integers $n$ and $k$ $(1 \leq n,k \leq 20000)$, the number of people at your house and the number of available cars. Then follow $n$ lines containing a single integer each; the $i$th such integer is the number of seconds $t_ i$$(1 \leq t_ i \leq 1000000)$ that it takes person $i$ to drive from your house to the stadium, or vice-versa.

-----Output-----
Print the minimum number of seconds it takes to move all $n$ people from your house to the stadium, if all people coordinate and drive optimally.

-----Examples-----
Sample Input:
11 2
12000
9000
4500
10000
12000
11000
12000
18000
10000
9000
12000
Sample Output:
13500

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