vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
You are given plans of rooms of polygonal shapes. The walls of the rooms on the plans are placed parallel to either x-axis or y-axis. In addition, the walls are made of special materials so they reflect light from sources as mirrors do, but only once. In other words, the walls do not reflect light already reflected at another point of the walls.

Now we have each room furnished with one lamp. Walls will be illuminated by the lamp directly or indirectly. However, since the walls reflect the light only once, some part of the walls may not be illuminated.

You are requested to write a program that calculates the total length of unilluminated part of the walls.

<image>

Figure 10: The room given as the second case in Sample Input



Input

The input consists of multiple test cases.

The first line of each case contains a single positive even integer N (4 ≤ N ≤ 20), which indicates the number of the corners. The following N lines describe the corners counterclockwise. The i-th line contains two integers xi and yi , where (xi , yi ) indicates the coordinates of the i-th corner. The last line of the case contains x' and y' , where (x' , y' ) indicates the coordinates of the lamp.

To make the problem simple, you may assume that the input meets the following conditions:

* All coordinate values are integers not greater than 100 in their absolute values.
* No two walls intersect or touch except for their ends.
* The walls do not intersect nor touch each other.
* The walls turn each corner by a right angle.
* The lamp exists strictly inside the room off the wall.
* The x-coordinate of the lamp does not coincide with that of any wall; neither does the y-coordinate.



The input is terminated by a line containing a single zero.

Output

For each case, output the length of the unilluminated part in one line. The output value may have an arbitrary number of decimal digits, but may not contain an error greater than 10-3 .

Example

Input

4
0 0
2 0
2 2
0 2
1 1
6
2 2
2 5
0 5
0 0
5 0
5 2
1 4
0


Output

0.000
3.000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
As an employee of the world’s most respected political polling corporation, you must take complex, real-world issues and simplify them down to a few numbers. It isn’t always easy. A big election is coming up and, at the request of Candidate X, you have just finished polling $n$ people. You have gathered three pieces of information from each person, with the values for the $i^\text {th}$ person recorded as:
 - $a_ i$ – the number of digits of $\pi $ they have memorized
 - $b_ i$ – the number of hairs on their head
 - $c_ i$ – whether they will vote for Candidate X

Unfortunately, you are beginning to wonder if these are really the most relevant questions to ask. In fact, you cannot see any correlation between $a$, $b$, and $c$ in the data. Of course, you cannot just contradict your customer – that is a good way to lose your job!

Perhaps the answer is to find some weighting formula to make the results look meaningful. You will pick two real values $S$ and $T$, and sort the poll results $(a_ i, b_ i, c_ i)$ by the measure $a_ i \cdot S + b_ i \cdot T$. The sort will look best if the results having $c_ i$ true are clustered as close to each other as possible. More precisely, if $j$ and $k$ are the indices of the first and last results with $c_ i$ true, you want to minimize the cluster size which is $k-j+1$. Note that some choices of $S$ and $T$ will result in ties among the $(a_ i,b_ i,c_ i)$ triples. When this happens, you should assume the worst possible ordering occurs (that which maximizes the cluster size for this $(S, T)$ pair).

-----Input-----
The input starts with a line containing $n$ ($1 \leq n \leq 250000$), which is the number of people polled. This is followed by one line for each person polled. Each of those lines contains integers $a_ i$ ($0 \leq a_ i \leq 2000000$), $b_ i$ ($0 \leq b_ i \leq 2000000$), and $c_ i$, where $c_ i$ is $1$ if the person will vote for Candidate X and $0$ otherwise. The input is guaranteed to contain at least one person who will vote for Candidate X.

-----Output-----
Display the smallest possible cluster size over all possible $(S, T)$ pairs.

-----Examples-----
Sample Input 1:
6
0 10 0
10 0 1
12 8 1
5 5 0
11 2 1
11 3 0
Sample Output 1:
4

Sample Input 2:
10
6 1 1
0 2 0
2 1 1
6 1 1
8 2 0
4 4 0
4 0 0
2 3 1
6 1 0
6 3 1
Sample Output 2:
8

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
"Point reflection" or "point symmetry" is a basic concept in geometry where a given point, P, at a given position relative to a mid-point, Q has a corresponding point, P1, which is the same distance from Q but in the opposite direction.

## Task

Given two points P and Q, output the symmetric point of point P about Q.
Each argument is a two-element array of integers representing the point's X and Y coordinates.  Output should be in the same format, giving the X and Y coordinates of point P1.  You do not have to validate the input.

This kata was inspired by the Hackerrank challenge [Find Point](https://www.hackerrank.com/challenges/find-point)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A necklace can be described as a string of links ('-') and pearls ('o'), with the last link or pearl connected to the first one. $0$ 

You can remove a link or a pearl and insert it between two other existing links or pearls (or between a link and a pearl) on the necklace. This process can be repeated as many times as you like, but you can't throw away any parts.

Can you make the number of links between every two adjacent pearls equal? Two pearls are considered to be adjacent if there is no other pearl between them.

Note that the final necklace should remain as one circular part of the same length as the initial necklace.


-----Input-----

The only line of input contains a string $s$ ($3 \leq |s| \leq 100$), representing the necklace, where a dash '-' represents a link and the lowercase English letter 'o' represents a pearl.


-----Output-----

Print "YES" if the links and pearls can be rejoined such that the number of links between adjacent pearls is equal. Otherwise print "NO".

You can print each letter in any case (upper or lower).


-----Examples-----
Input
-o-o--
Output
YES
Input
-o---

Output
YES
Input
-o---o-

Output
NO
Input
ooo

Output
YES

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You've got array a[1], a[2], ..., a[n], consisting of n integers. Count the number of ways to split all the elements of the array into three contiguous parts so that the sum of elements in each part is the same. 

More formally, you need to find the number of such pairs of indices i, j (2 ≤ i ≤ j ≤ n - 1), that $\sum_{k = 1}^{i - 1} a_{k} = \sum_{k = i}^{j} a_{k} = \sum_{k = j + 1}^{n} a_{k}$.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 5·10^5), showing how many numbers are in the array. The second line contains n integers a[1], a[2], ..., a[n] (|a[i]| ≤  10^9) — the elements of array a.


-----Output-----

Print a single integer — the number of ways to split the array into three parts with the same sum.


-----Examples-----
Input
5
1 2 3 0 3

Output
2

Input
4
0 1 -1 0

Output
1

Input
2
4 1

Output
0

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Petya and Gena play a very interesting game "Put a Knight!" on a chessboard *n*<=×<=*n* in size. In this game they take turns to put chess pieces called "knights" on the board so that no two knights could threat each other. A knight located in square (*r*,<=*c*) can threat squares (*r*<=-<=1,<=*c*<=+<=2), (*r*<=-<=1,<=*c*<=-<=2), (*r*<=+<=1,<=*c*<=+<=2), (*r*<=+<=1,<=*c*<=-<=2), (*r*<=-<=2,<=*c*<=+<=1), (*r*<=-<=2,<=*c*<=-<=1), (*r*<=+<=2,<=*c*<=+<=1) and (*r*<=+<=2,<=*c*<=-<=1) (some of the squares may be located outside the chessboard). The player who can't put a new knight during his move loses. Determine which player wins considering that both players play optimally well and Petya starts.

Input Specification:
The first line contains integer *T* (1<=≤<=*T*<=≤<=100) — the number of boards, for which you should determine the winning player. Next *T* lines contain *T* integers *n**i* (1<=≤<=*n**i*<=≤<=10000) — the sizes of the chessboards.

Output Specification:
For each *n**i*<=×<=*n**i* board print on a single line "0" if Petya wins considering both players play optimally well. Otherwise, print "1".

Demo Input:
['2\n2\n1\n']

Demo Output:
['1\n0\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Being a programmer, you like arrays a lot. For your birthday, your friends have given you an array a consisting of n distinct integers.

Unfortunately, the size of a is too small. You want a bigger array! Your friends agree to give you a bigger array, but only if you are able to answer the following question correctly: is it possible to sort the array a (in increasing order) by reversing exactly one segment of a? See definitions of segment and reversing in the notes.


-----Input-----

The first line of the input contains an integer n (1 ≤ n ≤ 10^5) — the size of array a.

The second line contains n distinct space-separated integers: a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ 10^9).


-----Output-----

Print "yes" or "no" (without quotes), depending on the answer.

If your answer is "yes", then also print two space-separated integers denoting start and end (start must not be greater than end) indices of the segment to be reversed. If there are multiple ways of selecting these indices, print any of them.


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

Output
yes
1 3

Input
4
2 1 3 4

Output
yes
1 2

Input
4
3 1 2 4

Output
no

Input
2
1 2

Output
yes
1 1



-----Note-----

Sample 1. You can reverse the entire array to get [1, 2, 3], which is sorted.

Sample 3. No segment can be reversed such that the array will be sorted.

Definitions

A segment [l, r] of array a is the sequence a[l], a[l + 1], ..., a[r].

If you have an array a of size n and you reverse its segment [l, r], the array will become:

a[1], a[2], ..., a[l - 2], a[l - 1], a[r], a[r - 1], ..., a[l + 1], a[l], a[r + 1], a[r + 2], ..., a[n - 1], a[n].

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Arya has a string, s, of uppercase English letters. She writes down the string s on a paper k times. She wants to calculate the occurence of a specific letter  in the first n characters of the final string.
Example
Input : 
s = "ABA"
k = 3
n = 7
c = 'B'
Output : 
2
Explaination : 
Final string - ABAABAABA
Example 
Input : 
s = "MMM"
k = 2
n = 4
c = 'M'
Output :
4
Explaination : 
Final string - MMMMMM
Ã¢â¬â¹Your Task:
You don't need to read input or print anything. Your task is to complete the function fun() which takes the string s , integer k ,integer n and the character c as input parameter and returns the occurence of the character c  in the first n characters of the final string.
Expected Time Complexity : O(|s|)
Expected Auxiliary Space : O(1)
Constraints:
1 <= |s| <= 10^{5}
1 <= k <= 10^{5}
1 <= n <= |s|*k

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a set $S$ and $Q$ queries. Initially, $S$ is empty. In each query:
- You are given a positive integer $X$.
- You should insert $X$ into $S$.
- For each $y \in S$ before this query such that $y \neq X$, you should also insert $y \oplus X$ into $S$ ($\oplus$ denotes the XOR operation).
- Then, you should find two values $E$ and $O$: the number of elements of $S$ with an even number of $1$-s and with an odd number of $1$-s in the binary representation, respectively.
Note that a set cannot have duplicate elements, so if you try to insert into $S$ an element that is already present in $S$, then nothing happens.

-----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 a single integer $Q$.
- Each of the next $Q$ lines contains a single integer $X$ describing a query.

-----Output-----
For each query, print a single line containing two space-separated integers $E$ and $O$.

-----Constraints-----
- $1 \le T \le 5$
- $1 \le Q, X \le 10^5$

-----Subtasks-----
Subtask #1 (30 points):
- $1 \le Q \le 1,000$
- $1 \le X \le 128$
Subtask #2 (70 points): original constraints

-----Example Input-----
1
3
4
2
7

-----Example Output-----
0 1
1 2
3 4

-----Explanation-----
Example case 1:
- Initially, the set is empty: $S = \{\}$.
- After the first query, $S = \{4\}$, so there is only one element with an odd number of $1$-s in the binary representation ("100").
- After the second query, $S = \{4,2,6\}$, there is one element with an even number of $1$-s in the binary representation ($6$ is "110") and the other two elements have an odd number of $1$-s.
- After the third query, $S = \{4,2,6,7,3,5,1\}$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Grandma Laura came to the market to sell some apples. During the day she sold all the apples she had. But grandma is old, so she forgot how many apples she had brought to the market.

She precisely remembers she had n buyers and each of them bought exactly half of the apples she had at the moment of the purchase and also she gave a half of an apple to some of them as a gift (if the number of apples at the moment of purchase was odd), until she sold all the apples she had.

So each buyer took some integral positive number of apples, but maybe he didn't pay for a half of an apple (if the number of apples at the moment of the purchase was odd).

For each buyer grandma remembers if she gave a half of an apple as a gift or not. The cost of an apple is p (the number p is even).

Print the total money grandma should have at the end of the day to check if some buyers cheated her.


-----Input-----

The first line contains two integers n and p (1 ≤ n ≤ 40, 2 ≤ p ≤ 1000) — the number of the buyers and the cost of one apple. It is guaranteed that the number p is even.

The next n lines contains the description of buyers. Each buyer is described with the string half if he simply bought half of the apples and with the string halfplus if grandma also gave him a half of an apple as a gift.

It is guaranteed that grandma has at least one apple at the start of the day and she has no apples at the end of the day.


-----Output-----

Print the only integer a — the total money grandma should have at the end of the day.

Note that the answer can be too large, so you should use 64-bit integer type to store it. In C++ you can use the long long integer type and in Java you can use long integer type.


-----Examples-----
Input
2 10
half
halfplus

Output
15

Input
3 10
halfplus
halfplus
halfplus

Output
55



-----Note-----

In the first sample at the start of the day the grandma had two apples. First she sold one apple and then she sold a half of the second apple and gave a half of the second apple as a present to the second buyer.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Little girl Tanya is learning how to decrease a number by one, but she does it wrong with a number consisting of two or more digits. Tanya subtracts one from a number by the following algorithm:  if the last digit of the number is non-zero, she decreases the number by one;  if the last digit of the number is zero, she divides the number by 10 (i.e. removes the last digit). 

You are given an integer number $n$. Tanya will subtract one from it $k$ times. Your task is to print the result after all $k$ subtractions.

It is guaranteed that the result will be positive integer number.


-----Input-----

The first line of the input contains two integer numbers $n$ and $k$ ($2 \le n \le 10^9$, $1 \le k \le 50$) — the number from which Tanya will subtract and the number of subtractions correspondingly.


-----Output-----

Print one integer number — the result of the decreasing $n$ by one $k$ times.

It is guaranteed that the result will be positive integer number. 


-----Examples-----
Input
512 4

Output
50

Input
1000000000 9

Output
1



-----Note-----

The first example corresponds to the following sequence: $512 \rightarrow 511 \rightarrow 510 \rightarrow 51 \rightarrow 50$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A new lord assumed the position by the death of the previous lord in a Far Eastern province.

The new greedy lord hates concave polygons, because he believes they need much wasted area to be drawn on paper. He always wants to modify them to convex ones.

His castle is currently surrounded by a wall forming a concave polygon, when seen from the above. Of course he hates it. He believes more area could be obtained with a wall of a convex polygon. Thus he has ordered his vassals to have new walls built so they form a convex polygon.

Unfortunately, there is a limit in the budget. So it might be infeasible to have the new walls built completely. The vassals has found out that only up to r meters of walls in total can be built within the budget. In addition, the new walls must be built in such a way they connect the polygonal vertices of the present castle wall. It is impossible to build both of intersecting walls.

After long persuasion of the vassals, the new lord has reluctantly accepted that the new walls might not be built completely. However, the vassals still want to maximize the area enclosed with the present and new castle walls, so they can satisfy the lord as much as possible.

Your job is to write a program to calculate, for a given integer r, the maximum possible area of the castle with the new walls.



Input

The input file contains several test cases.

Each case begins with a line containing two positive integers n and r. n is the number of vertices of the concave polygon that describes the present castle wall, satisfying 5 ≤ n ≤ 64. r is the maximum total length of new castle walls feasible within the budget, satisfying 0 ≤ r ≤ 400.

The subsequent n lines are the x- and y-coordinates of the n vertices. The line segments (xi, yi) - (xi+1, yi+1) (1 ≤ i ≤ n - 1) and (xn, yn) - (x1, y1) form the present castle wall of the concave polygon. Those coordinates are given in meters and in the counterclockwise order of the vertices.

All coordinate values are integers between 0 and 100, inclusive. You can assume that the concave polygon is simple, that is, the present castle wall never crosses or touches itself.

The last test case is followed by a line containing two zeros.

Output

For each test case in the input, print the case number (beginning with 1) and the maximum possible area enclosed with the present and new castle walls. The area should be printed with exactly one fractional digit.

Example

Input

5 4
0 0
4 0
4 4
2 2
0 4
8 80
45 41
70 31
86 61
72 64
80 79
40 80
8 94
28 22
0 0


Output

case 1: 16.0
case 2: 3375.0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider an N \times M binary matrix A, i.e. a grid consisting of N rows numbered 1 to N from top to bottom and M columns numbered 1 to M from left to right, whose cells take the value 0 or 1. Let (i, j) denote the cell on the i-th row and j-th column.

The matrix is said to be *special* if for every cell (i, j), the following condition holds simultaneously:
A_{i, j} = 1 if and only if the sum of row i is equal to the sum of column j. More formally, A_{i, j} = 1 iff \displaystyle\sum_{k=1}^{M} A_{i, k} = \sum_{k=1}^{N} A_{k, j}

The *specialty* of a *special* matrix is defined to be the sum of values of all cells in the matrix. Given N and M, find the minimum *specialty* of a *special* matrix among all *special* binary matrices consisting of N rows and M columns.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of a single line containing N and M — the number of rows and the number of columns.

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

For each test case, output on a new line the minimum *specialty* of a *special* matrix among all *special* binary matrices consisting of N rows and M columns.

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ N, M ≤ 5000$

----- Sample Input 1 ------ 
2
3 3
4 5
----- Sample Output 1 ------ 
5
10
----- explanation 1 ------ 
Test case 1: One such *special* binary matrix with minimum *specialty* is:

Test case 2: One such *special* binary matrix with minimum *specialty* is:

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bob gives you a list of  N strings and a task to solve. The task is to remove all the duplicate strings from the list and print the resulting list of strings in a sorted order.

Input:
The first line contains  an integer N. Then next N lines contain a  string Si.

Output:
Print the sorted list.

Constraints:
1 ≤ |N| ≤ 5000
1 ≤ |Si| ≤ 100

SAMPLE INPUT
16
nandu 
kanth
kalyan
dhiraj
kanth
kalyan
baala
kt
baala
jayanth
sampu
baala
kanth
kalyan
baala
kt

SAMPLE OUTPUT
baala
dhiraj
jayanth
kalyan
kanth
kt
nandu
sampu

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Burger Town is a city that consists of $N$ special junctions and $N-1$ pathways. There is exactly one shortest path between each pair of junctions. Junction $\boldsymbol{i}$ is located at $(x_i,y_i)$ and the distance between two junctions $i,j$ is defined by the Taxicab geometry. 

Tim has recently afforded a taxicab to work as a taxicab driver. His vehicle was very cheap, but has a very big flaw. It can only drive $\mbox{H}$ units horizontally and $\mbox{V}$ units vertically before refueling. 

If a customer wants to be brought from a junction $\boldsymbol{i}$ to another junction $j$, then this car is only capable of driving the route, iff the sum of horizontal distances and the sum of vertical distances on this path are less than or equal to $\mbox{H}$ and $\mbox{V}$ respectively. 

Also, there is a unique path between any two junctions.  

Now he has thoughts about returning the vehicle back to the seller. But he first wants to know, if it's even worth it. That's why he wants to know the number of unordered pairs $(i,j)$ such that it is not possible to drive a customer from junction $\boldsymbol{i}$ to junction $j$. 

Input Format

On the first line you will be given $N$, $\mbox{H}$ and $\mbox{V}$ separated by a single space. 

Each of the next $N$ lines contains two space separated integers $x_i,y_i$, denoting the location of junction $\boldsymbol{i}$.
Each of the next $N-1$ lines contains two space separated integers describing a path existing between $u_{i},v_{i}$, i.e., there is a path between $u_i$ and $v_i$.  

Output Format

Output the number of unordered pairs $(i,j)$ such that it is not possible to drive from $\boldsymbol{i}$ to $j$. 

Constraints

$2\leq N\leq10^5$

$0\leq H,V\leq10^{14}$

$0\leq x_i,y_i\leq10^9$

Sample Input

3 2 1
0 0
1 1
2 0
1 2
2 3

Sample Output

1

Explanation

The car is only capable of driving $H=2$ units horizontally and $V=1$ unit vertically. The horizontal distance between junction 1 and 3(via 2) is equal to 2($\textbf{0}\to1\to2$), which fits under the horizontal limit of the car. The vertical distance between 1 and 3 is also equal to 2($\textbf{0}\to1\to0$), but this is not possible for this car since $2>V$.

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