vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Bob Bubblestrong just got a new job as security guard. Bob is now responsible for safety of a collection of warehouses, each containing the most valuable Bubble Cup assets - the high-quality bubbles. His task is to detect thieves inside the warehouses and call the police.

Looking from the sky, each warehouse has a shape of a convex polygon. Walls of no two warehouses intersect, and of course, none of the warehouses is built inside of another warehouse.

Little did the Bubble Cup bosses know how lazy Bob is and that he enjoys watching soap operas (he heard they are full of bubbles) from the coziness of his office. Instead of going from one warehouse to another to check if warehouses are secured, the plan Bob has is to monitor all the warehouses from the comfort of his office using the special X-ray goggles. The goggles have an infinite range, so a thief in any of the warehouses could easily be spotted.

However, the goggles promptly broke and the X-rays are now strong only enough to let Bob see through a single wall. Now, Bob would really appreciate if you could help him find out what is the total area inside of the warehouses monitored by the broken goggles, so that he could know how much area of the warehouses he needs to monitor in person.

Input

The first line contains one integer N (1 ≤ N ≤ 10^4) – the number of warehouses.

The next N lines describe the warehouses.

The first number of the line is integer c_i (3 ≤ c_i ≤ 10^4) – the number corners in the i^{th} warehouse, followed by c_i pairs of integers. The j^{th} pair is (x_j, y_j) – the coordinates of the j^{th} corner (|x_j|, |y_j| ≤ 3 * 10^4). The corners are listed in the clockwise order. The total number of corners in all the warehouses is at most 5 * 10^4.

Bob's office is positioned at the point with coordinates (0, 0). The office is not contained within any of the warehouses.

Output

Print a single line containing a single decimal number accurate to at least four decimal places – the total area of the warehouses Bob can monitor using the broken X-ray goggles.

Example

Input


5
4 1 1 1 3 3 3 3 1
4 4 3 6 2 6 0 4 0
6 -5 3 -4 4 -3 4 -2 3 -3 2 -4 2
3 0 -1 1 -3 -1 -3
4 1 -4 1 -6 -1 -6 -1 -4


Output


13.333333333333

Note

<image>

Areas monitored by the X-ray goggles are colored green and areas not monitored by the goggles are colored red.

The warehouses ABCD, IJK and LMNOPQ are completely monitored using the googles.

The warehouse EFGH is partially monitored using the goggles: part EFW is not monitored because to monitor each point inside it, the X-rays must go through two walls of warehouse ABCD.

The warehouse RUTS is not monitored from the Bob's office, because there are two walls of the warehouse IJK between Bob's office and each point in RUTS.

The total area monitored by the goggles is P = P_{ABCD} + P_{FGHW} + P_{IJK} + P_{LMNOPQ} = 4 + 3.333333333333 + 2 + 4 = 13.333333333333.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Sereja owns a restaurant for n people. The restaurant hall has a coat rack with n hooks. Each restaurant visitor can use a hook to hang his clothes on it. Using the i-th hook costs a_{i} rubles. Only one person can hang clothes on one hook.

Tonight Sereja expects m guests in the restaurant. Naturally, each guest wants to hang his clothes on an available hook with minimum price (if there are multiple such hooks, he chooses any of them). However if the moment a guest arrives the rack has no available hooks, Sereja must pay a d ruble fine to the guest. 

Help Sereja find out the profit in rubles (possibly negative) that he will get tonight. You can assume that before the guests arrive, all hooks on the rack are available, all guests come at different time, nobody besides the m guests is visiting Sereja's restaurant tonight.


-----Input-----

The first line contains two integers n and d (1 ≤ n, d ≤ 100). The next line contains integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 100). The third line contains integer m (1 ≤ m ≤ 100).


-----Output-----

In a single line print a single integer — the answer to the problem.


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

Output
3

Input
2 1
2 1
10

Output
-5



-----Note-----

In the first test both hooks will be used, so Sereja gets 1 + 2 = 3 rubles.

In the second test both hooks will be used but Sereja pays a fine 8 times, so the answer is 3 - 8 =  - 5.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
### The Story:
Bob is working as a bus driver. However, he has become extremely popular amongst the city's residents. With so many passengers wanting to get aboard his bus, he sometimes has to face the problem of not enough space left on the bus! He wants you to write a simple program telling him if he will be able to fit all the passengers.

### Task Overview:

You have to write a function that accepts three parameters: 
* `cap` is the amount of people the bus can hold excluding the driver.
* `on` is the number of people on the bus.
* `wait` is the number of people waiting to get on to the bus. 

If there is enough space, return 0, and if there isn't, return the number of passengers he can't take.

### Usage Examples:

```python
enough(10, 5, 5)
0 # He can fit all 5 passengers
enough(100, 60, 50)
10 # He can't fit 10 out of 50 waiting
```

```if:csharp
Documentation:
Kata.Enough Method (Int32, Int32, Int32)

Returns the number of passengers the bus cannot fit, or 0 if the bus can fit every passenger.

Syntax


public
static
int Enough(
int cap,
    int on,
int wait
    )
  



Parameters

cap

Type: System.Int32
The amount of people that can fit on the bus excluding the driver.

on

Type: System.Int32
The amount of people on the bus excluding the driver.

wait

Type: System.Int32
The amount of people waiting to enter the bus.

Return Value

Type: System.Int32
  An integer representing how many passengers cannot fit on the bus, or 0 if every passenger can fit on the bus.

```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Sandra recently bought her first smart phone. One of her friends suggested a long list of applications (more commonly known as “apps”) that she should install on the phone. Sandra immediately started installing the apps from the list, but after installing a few, the phone did not have enough disk space to install any more apps. Sometimes, the app installation failed because there was not even enough space to download the installation package. Other apps could be downloaded just fine, but had insufficient space to store the installed app. 

Each app that Sandra installs has a download size $d$ and a storage size $s$. To download the app, Sandra’s phone must have at least $d$ megabytes of free disk space. After the app has been installed, it then uses $s$ megabytes of disk space on the phone. The download size may be smaller than the storage size (e.g., if the app data is heavily compressed) or larger than the storage size (e.g., if the download contains material that might not get used such as translations to different languages). The installer is very efficient and can transform the downloaded package to an installed app without using any extra disk space. Thus, to install an app, the phone must have at least $\max (d, s)$ megabytes of free disk space.

Sandra quickly realised that she may have run out of space just because she installed apps in the wrong order. Thus, she decided to give the installation another try. She uninstalled all apps, and will now choose an installation order that lets her install the largest number of apps from the list. Sandra may not install any app more than once.

Help her determine what apps on the list she should install, and in what order.

-----Input-----
The input consists of:
 - One line with two integers $n$, $c$ ($1 \le n \le 500, 1 \le c \le 10000$), the number of available apps and the available disk space of the phone in megabytes.
 - $n$ lines, each with two integers $d, s$ ($1 \le d, s \le 10000$), the download size and storage size of an app, in megabytes.

-----Output-----
Output one line with the maximum number of apps that can be installed. Then output one line listing the numbers of those apps, in the order that Sandra should install them. In the case that no apps can be installed, this line can be omitted.

The apps are numbered from $1$ to $n$, in the order they are given in the input. If there are multiple optimal solutions, output any one of them.

-----Examples-----
Sample Input:
2 100
99 1
1 99
Sample Output:
2
1 2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Problem D: Exportation in Space

In an era of space travelling, Mr. Jonathan A. Goldmine exports a special material named "Interstellar Condensed Powered Copper". A piece of it consists of several spheres floating in the air. There is strange force affecting between the spheres so that their relative positions of them are not changed. If you move one of them, all the others follow it.

<image>
Example of ICPC (left: bare, right: shielded)

To transport ICPCs between planets, it needs to be shielded from cosmic rays. It will be broken when they hit by strong cosmic rays. Mr. Goldmine needs to wrap up each ICPC pieces with anti-cosmic-ray shield, a paper-like material which cuts all the cosmic rays. To save cost, he wants to know the minimum area of the shield he needs to wrap an ICPC piece up.

Note that he can't put the shield between the spheres of an ICPC because it affects the force between the spheres. So that the only way to shield it is to wrap the whole ICPC piece by shield.

Mr. Goldmine asked you, an experienced programmer, to calculate the minimum area of shield for each material.

You can assume that each sphere in an ICPC piece is a point, and you can ignore the thickness of the shield.



Input

Each file consists of one test case, which has the information of one ICPC piece. A test case starts with a line with an integer N (4 <= N <= 50), denoting the number of spheres in the piece of the test case. Then N lines follow. The i-th line of them describes the position of the i-th sphere. It has 3 integers xi, yi and zi (0 <= x, y, z <= 100), separated by a space. They denote the x, y and z coordinates of the i-th sphere, respectively.

It is guaranteed that there are no data all of whose spheres are on the same plane, and that no two spheres in a data are on the same coordinate.

Output

For each input, print the area of the shield Mr. Goldmine needs. The output value should be in a decimal fraction and should not contain an error greater than 0.001.

Examples

Input

4
0 0 0
0 0 1
0 1 0
1 0 0


Output

2.366


Input

8
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1


Output

6.000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
As you may know, once some people pass their teens, they jokingly only celebrate their 20th or 21st birthday, forever. With some maths skills, that's totally possible - you only need to select the correct number base!

For example, if they turn 32, that's exactly 20 - in base 16... Already 39? That's just 21, in base 19!

Your task is to translate the given age to the much desired 20 (or 21) years, and indicate the number base, in the format specified below.

**Note:** input will be always > 21


### Examples:

```
32  -->  "32? That's just 20, in base 16!"
39  -->  "39? That's just 21, in base 19!"
```

*Hint: if you don't know (enough) about [numeral systems](https://en.wikipedia.org/wiki/Numeral_system) and [radix](https://en.wikipedia.org/wiki/Radix), just observe the pattern!*

---

## My other katas

If you enjoyed this kata then please try [my other katas](https://www.codewars.com/collections/katas-created-by-anter69)! :-)

---

### *Translations are welcome!*

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef has a permutation P of length 2 \cdot N. He can perform the following operation on P:
Select an index i (1 ≤ i < 2 \cdot N) and swap P_{i} and P_{i + 1}.

Chef would call the permutation P *good*, if the maximum element of the first half of P is less than the minimum element of the second half of P.  
Formally \displaystyle \max_{(1 ≤ i ≤ N)} P_{i} < \min_{(N < i ≤ 2 \cdot N)} P_{i}.

Find the minimum number of operations Chef needs to apply to make P *good*.

Note: A permutation of length N is an array where every integer from 1 to N occurs exactly once.

------ Input Format ------ 

- The first line contains a single integer T — the number of test cases. Then the test cases follow.
- The first line of each test case contains an integer N — half the size of the permutation P.
- The second line of each test case contains 2 \cdot N space-separated integers P_{1}, P_{2}, \dots, P_{2 \cdot N} denoting the permutation P.

------ Output Format ------ 

For each test case, output the minimum number of operations required to make P *good*.

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
$P$ is a permutation of length $2 \cdot N$
- The sum of $N$ over all test cases won't exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------ 
3
2
3 2 1 4
3
1 2 3 4 5 6
3
6 5 4 3 2 1

----- Sample Output 1 ------ 
2
0
9

----- explanation 1 ------ 
Test case $1$: We can perform the following operations:
- Apply operation at $i = 1$: $[3, 2, 1, 4] \rightarrow [2, 3, 1, 4]$
- Apply operation at $i = 2$: $[2, 3, 1, 4] \rightarrow [2, 1, 3, 4]$

Test case $2$: $P$ is already good.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Write a function that takes a number or a string and gives back the number of **permutations without repetitions** that can generated using all of its element.; more on permutations [here](https://en.wikipedia.org/wiki/Permutation).

For example, starting with:
```
1
45
115
"abc"
```

You could respectively generate:
```
1
45,54
115,151,511
"abc","acb","bac","bca","cab","cba"
```

So you should have, in turn:
```python
perms(1)==1
perms(45)==2
perms(115)==3
perms("abc")==6
```

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

problem

Given a permutation of length N, a_1, a_2, ..., a_N, which is a permutation of integers from 1 to N. Also, Q queries are given in order for this permutation. In the i-th query, you have to do the following:

* The value q_i (1 \ leq q_i \ leq N) is given. In the permutation \\ {a_1, a_2, ..., a_N \\}, where L is the permutation on the left side of q_i and R is the permutation on the right side of q_i, the original permutation L \\ q_i \\ R is R \\ Change to q_i \\ L. That is, when q_ {i} = a_j, the permutations \\ {a_1, ..., a_ {j-1}, a_j, a_ {j + 1}, ..., a_N \\} are \\ { Change to a_ {j + 1}, ..., a_N, a_j, a_1, ..., a_ {j-1} \\}.



The permutations L and R may be empty. For example, if L is empty, change q_i \\ R to R \\ q_i. The same is true when R is empty.

Output the permutation after processing these Q queries in order for the given permutation on one line.

Input format


N Q
a_1 a_2 ... a_N
q_1 q_2 ... q_Q


All inputs are integers.

The first row gives the number of elements in the permutation N and the number of queries Q, separated by blanks. In the second line, permutations a_1, a_2, ..., a_N, in which integers from 1 to N are rearranged, are given separated by blanks. The third line gives Q queries, separated by blanks. q_i represents the i-th query.

Constraint

* 1 \ leq N \ leq 10 ^ 5
* 1 \ leq Q \ leq 10 ^ 5
* 1 \ leq a_i \ leq N
* a_i is different
* 1 \ leq q_i \ leq N



Output format

Output the permutation after processing all the queries in order on one line.

Input example 1


5 2
1 5 3 2 4
5 2


Output example 1


4 5 1 2 3

* The first query changes the permutation to \\ {3, 2, 4, 5, 1 \\}.
* The second query changes the permutation to \\ {4, 5, 1, 2, 3 \\}.



Input example 2


5 1
1 2 3 4 5
Five


Output example 2


5 1 2 3 4





Example

Input

5 2
1 5 3 2 4
5 2


Output

4 5 1 2 3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a positive integer $n$. In one move, you can increase $n$ by one (i.e. make $n := n + 1$). Your task is to find the minimum number of moves you need to perform in order to make the sum of digits of $n$ be less than or equal to $s$.

You have to answer $t$ independent test cases.


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 2 \cdot 10^4$) — the number of test cases. Then $t$ test cases follow.

The only line of the test case contains two integers $n$ and $s$ ($1 \le n \le 10^{18}$; $1 \le s \le 162$).


-----Output-----

For each test case, print the answer: the minimum number of moves you need to perform in order to make the sum of digits of $n$ be less than or equal to $s$.


-----Example-----
Input
5
2 1
1 1
500 4
217871987498122 10
100000000000000001 1

Output
8
0
500
2128012501878
899999999999999999

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a collection of Intervals, the task is to merge all of the overlapping Intervals.
Example 1:
Input:
Intervals = {{1,3},{2,4},{6,8},{9,10}}
Output: {{1, 4}, {6, 8}, {9, 10}}
Explanation: Given intervals: [1,3],[2,4]
[6,8],[9,10], we have only two overlapping
intervals here,[1,3] and [2,4]. Therefore
we will merge these two and return [1,4],
[6,8], [9,10].
Example 2:
Input:
Intervals = {{6,8},{1,9},{2,4},{4,7}}
Output: {{1, 9}}
Your Task:
Complete the function overlappedInterval() that takes the list N intervals as input parameters and returns sorted list of intervals after merging.
Expected Time Complexity: O(N*Log(N)).
Expected Auxiliary Space: O(Log(N)) or O(N).
Constraints:
1 ≤ N ≤ 100
0 ≤ x ≤ y ≤ 1000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Long story short, shashlik is Miroslav's favorite food. Shashlik is prepared on several skewers simultaneously. There are two states for each skewer: initial and turned over.

This time Miroslav laid out n skewers parallel to each other, and enumerated them with consecutive integers from 1 to n in order from left to right. For better cooking, he puts them quite close to each other, so when he turns skewer number i, it leads to turning k closest skewers from each side of the skewer i, that is, skewers number i - k, i - k + 1, ..., i - 1, i + 1, ..., i + k - 1, i + k (if they exist). 

For example, let n = 6 and k = 1. When Miroslav turns skewer number 3, then skewers with numbers 2, 3, and 4 will come up turned over. If after that he turns skewer number 1, then skewers number 1, 3, and 4 will be turned over, while skewer number 2 will be in the initial position (because it is turned again).

As we said before, the art of cooking requires perfect timing, so Miroslav wants to turn over all n skewers with the minimal possible number of actions. For example, for the above example n = 6 and k = 1, two turnings are sufficient: he can turn over skewers number 2 and 5.

Help Miroslav turn over all n skewers.

Input

The first line contains two integers n and k (1 ≤ n ≤ 1000, 0 ≤ k ≤ 1000) — the number of skewers and the number of skewers from each side that are turned in one step.

Output

The first line should contain integer l — the minimum number of actions needed by Miroslav to turn over all n skewers. After than print l integers from 1 to n denoting the number of the skewer that is to be turned over at the corresponding step.

Examples

Input

7 2


Output

2
1 6 


Input

5 1


Output

2
1 4 

Note

In the first example the first operation turns over skewers 1, 2 and 3, the second operation turns over skewers 4, 5, 6 and 7.

In the second example it is also correct to turn over skewers 2 and 5, but turning skewers 2 and 4, or 1 and 5 are incorrect solutions because the skewer 3 is in the initial state after these operations.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Will the galaxy see peace at last? All the warlords have gathered to divide all of space between themselves. The negotiations have come quite far and the warlords have finally agreed on a peaceful way of deciding who gets what. The $2$-dimensional galactic map must first be divided into sectors by splitting it along a set of infinite lines. The warlord with the largest battle fleet will choose one sector, then the warlord with the second largest fleet will choose some other sector and so on, until everyone has gotten a sector. This is then repeated until there are no sectors left.

Different sets of lines have been suggested, and it is up to you to present these alternatives to the meeting. To make sure that there will be peace, you are ready to modify the suggestions slightly. You have some experience with warlords and know that no warlord will settle for less space than anyone else, so for there to be peace, all of them must get the exact same area on the map. Since space is infinite, so is the map. Some sectors therefore have infinite area, so that is the amount of space everyone wants. How many extra lines do you have to add to make sure each warlord can get at least one sector with infinite area?

-----Input-----
The first line of input contains two positive integers $W$ and $N$, ($1 \leq W,N \leq 100$) denoting the number of warlords and the number of lines in the suggested division of space. This is followed by $N$ lines each containing four integers $x_1$, $y_1$, $x_2$ and $y_2$, each with an absolute value no higher than $10000$. This means that one line is intersecting the two points $(x_1,y_1)$ and $(x_2,y_2)$ on the galactic map. These two points are not be the same.

-----Output-----
Output the number of lines you have to add to this suggestion to satisfy all warlords.

-----Examples-----
Sample Input:
2 1
1 1 -2 0
Sample Output:
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Write a program which reads an integer n and draws a Koch curve based on recursive calles of depth n.

The Koch curve is well known as a kind of fractals.

You can draw a Koch curve in the following algorithm:

* Divide a given segment (p1, p2) into three equal segments.
* Replace the middle segment by the two sides of an equilateral triangle (s, u, t) of the same length as the segment.
* Repeat this procedure recursively for new segments (p1, s), (s, u), (u, t), (t, p2).

<image>

You should start (0, 0), (100, 0) as the first segment.

Notes

Constraints

* 0 ≤ n ≤ 6

Input

An integer n is given.

Output

Print each point (x, y) of the Koch curve. Print a point in a line. You should start the point(0, 0), which is the endpoint of the first segment and end with the point (100, 0), the other endpoint so that you can draw the Koch curve as an unbroken line. Each solution should be given as a decimal with an arbitrary number of fractional digits, and with an absolute error of at most 10-4.

Examples

Input

1


Output

0.00000000 0.00000000
33.33333333 0.00000000
50.00000000 28.86751346
66.66666667 0.00000000
100.00000000 0.00000000


Input

2


Output

0.00000000 0.00000000
11.11111111 0.00000000
16.66666667 9.62250449
22.22222222 0.00000000
33.33333333 0.00000000
38.88888889 9.62250449
33.33333333 19.24500897
44.44444444 19.24500897
50.00000000 28.86751346
55.55555556 19.24500897
66.66666667 19.24500897
61.11111111 9.62250449
66.66666667 0.00000000
77.77777778 0.00000000
83.33333333 9.62250449
88.88888889 0.00000000
100.00000000 0.00000000

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