vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Girl Lena likes it when everything is in order, and looks for order everywhere. Once she was getting ready for the University and noticed that the room was in a mess — all the objects from her handbag were thrown about the room. Of course, she wanted to put them back into her handbag. The problem is that the girl cannot carry more than two objects at a time, and cannot move the handbag. Also, if he has taken an object, she cannot put it anywhere except her handbag — her inherent sense of order does not let her do so.

You are given the coordinates of the handbag and the coordinates of the objects in some Сartesian coordinate system. It is known that the girl covers the distance between any two objects in the time equal to the squared length of the segment between the points of the objects. It is also known that initially the coordinates of the girl and the handbag are the same. You are asked to find such an order of actions, that the girl can put all the objects back into her handbag in a minimum time period.

Input

The first line of the input file contains the handbag's coordinates xs, ys. The second line contains number n (1 ≤ n ≤ 24) — the amount of objects the girl has. The following n lines contain the objects' coordinates. All the coordinates do not exceed 100 in absolute value. All the given positions are different. All the numbers are integer.

Output

In the first line output the only number — the minimum time the girl needs to put the objects into her handbag. 

In the second line output the possible optimum way for Lena. Each object in the input is described by its index number (from 1 to n), the handbag's point is described by number 0. The path should start and end in the handbag's point. If there are several optimal paths, print any of them. 

Examples

Input

0 0
2
1 1
-1 1


Output

8
0 1 2 0 


Input

1 1
3
4 3
3 4
0 0


Output

32
0 1 2 0 3 0 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ashi is interested in checking the algorithmic skills of her boyfriend. So, she sets up a special 2-D graph for him. The 2-D graph looks like a maze with N rows each containing N nodes.
To connect these nodes, Ashi uses the following algorithm:
 She selects two integers k1, k2 and computes the k1^th and k2^th fibonacci number, fib(k1) and fib(k2) respectively. 
 She takes the first row and selects the first two nodes in that row and adds an edge of weight (fib(k1) + fib(k2))%MOD. For, the next pair of consecutive nodes, she adds an edge of weight (fib(k1+1) + fib(k2+1))%MOD, then for the next pair (fib(k1+2) + fib(k2+2))%MOD and so on till the end of the row.
 For the remaining rows, she uses the same algorithm incrementing the fibonacci number the same way as earlier.
 Then she selects two more integers k3 and k4 and computes fib(k3) and fib(k4) respectively.
 She, like filling rows, fills the columns by starting from the first column, finish adding edges in that and then move on to the next column

She wants her boyfriend to select a subset of edges such that all the nodes are connected with each other by some path and the total sum of edges in the subset is minimum over all possible subsets of edges that maintain the connectivity of the graph.
Input:

There is only one line in input containing five space separated integers:
N k1 k2 k3 k4

Output:
Desired Output. 
Constraints:
1 ≤ N ≤ 1000
1 ≤ k1, k2, k3, k4 ≤ 1000000000000000000
MOD = 1000000007

SAMPLE INPUT
2 1 2 3 4

SAMPLE OUTPUT
10

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Complete the function to find the count of the most frequent item of an array. You can assume that input is an array of integers. For an empty array return `0`

## Example
```python
input array: [3, -1, -1, -1, 2, 3, -1, 3, -1, 2, 4, 9, 3]
ouptut: 5 
```
The most frequent number in the array is `-1` and it occurs `5` times.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Polycarp's workday lasts exactly $n$ minutes. He loves chocolate bars and can eat one bar in one minute. Today Polycarp has $k$ bars at the beginning of the workday.

In some minutes of the workday Polycarp has important things to do and in such minutes he is not able to eat a chocolate bar. In other minutes he can either eat or not eat one chocolate bar. It is guaranteed, that in the first and in the last minutes of the workday Polycarp has no important things to do and he will always eat bars in this minutes to gladden himself at the begining and at the end of the workday. Also it is guaranteed, that $k$ is strictly greater than $1$.

Your task is to determine such an order of eating chocolate bars that the maximum break time between eating bars is as minimum as possible.

Consider that Polycarp eats a bar in the minute $x$ and the next bar in the minute $y$ ($x &lt; y$). Then the break time is equal to $y - x - 1$ minutes. It is not necessary for Polycarp to eat all bars he has.

Input Specification:
The first line contains two integers $n$ and $k$ ($2 \le n \le 200\,000$, $2 \le k \le n$) — the length of the workday in minutes and the number of chocolate bars, which Polycarp has in the beginning of the workday.

The second line contains the string with length $n$ consisting of zeros and ones. If the $i$-th symbol in the string equals to zero, Polycarp has no important things to do in the minute $i$ and he can eat a chocolate bar. In the other case, Polycarp is busy in the minute $i$ and can not eat a chocolate bar. It is guaranteed, that the first and the last characters of the string are equal to zero, and Polycarp always eats chocolate bars in these minutes.

Output Specification:
Print the minimum possible break in minutes between eating chocolate bars.

Demo Input:
['3 3\n010\n', '8 3\n01010110\n']

Demo Output:
['1\n', '3\n']

Note:
In the first example Polycarp can not eat the chocolate bar in the second minute, so the time of the break equals to one minute.

In the second example Polycarp will eat bars in the minutes $1$ and $8$ anyway, also he needs to eat the chocolate bar in the minute $5$, so that the time of the maximum break will be equal to $3$ minutes.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Implication is a function of two logical arguments, its value is false if and only if the value of the first argument is true and the value of the second argument is false. 

Implication is written by using character '<image>', and the arguments and the result of the implication are written as '0' (false) and '1' (true). According to the definition of the implication: 

<image>

<image>

<image>

<image>

When a logical expression contains multiple implications, then when there are no brackets, it will be calculated from left to fight. For example,

<image>. 

When there are brackets, we first calculate the expression in brackets. For example,

<image>.

For the given logical expression <image> determine if it is possible to place there brackets so that the value of a logical expression is false. If it is possible, your task is to find such an arrangement of brackets.

Input

The first line contains integer n (1 ≤ n ≤ 100 000) — the number of arguments in a logical expression.

The second line contains n numbers a1, a2, ..., an (<image>), which means the values of arguments in the expression in the order they occur.

Output

Print "NO" (without the quotes), if it is impossible to place brackets in the expression so that its value was equal to 0.

Otherwise, print "YES" in the first line and the logical expression with the required arrangement of brackets in the second line.

The expression should only contain characters '0', '1', '-' (character with ASCII code 45), '>' (character with ASCII code 62), '(' and ')'. Characters '-' and '>' can occur in an expression only paired like that: ("->") and represent implication. The total number of logical arguments (i.e. digits '0' and '1') in the expression must be equal to n. The order in which the digits follow in the expression from left to right must coincide with a1, a2, ..., an.

The expression should be correct. More formally, a correct expression is determined as follows:

  * Expressions "0", "1" (without the quotes) are correct. 
  * If v1, v2 are correct, then v1->v2 is a correct expression. 
  * If v is a correct expression, then (v) is a correct expression. 



The total number of characters in the resulting expression mustn't exceed 106.

If there are multiple possible answers, you are allowed to print any of them.

Examples

Input

4
0 1 1 0


Output

YES
(((0)-&gt;1)-&gt;(1-&gt;0))


Input

2
1 1


Output

NO


Input

1
0


Output

YES
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Kitty and Katty have $N$ plastic blocks. They label the blocks with sequential numbers from $\mbox{1}$ to $N$ and begin playing a game in turns, with Kitty always taking the first turn. The game's rules are as follows:

For each turn, the player removes $2$ blocks, $\mbox{A}$ and $\mbox{B}$, from the set. They calculate $A-B$, write the result on a new block, and insert the new block into the set. 
The game ends when only $\mbox{1}$ block is left. The winner is determined by the value written on the final block, $\mbox{X}$:
If $X\%3=1$, then Kitty wins.
If $X\%3=2$, then Katty wins.
If $X\%3=0$, then the player who moved last wins.

Recall that $\%$ is the Modulo Operation.

Given the value of $N$, can you find and print the name of the winner? Assume that both play optimally.

Note: The selection order for $\mbox{A}$ and $\mbox{B}$ matters, as sometimes $A-B\neq B-A$. The diagram below shows an initial set of blocks where $N=5$. If $A=2$ and $B=3$, then the newly inserted block is labeled $-1$; alternatively, if $A=3$ and $B=2$, the newly inserted block is labeled $\mbox{1}$.

Input Format

The first line contains a single positive integer, $\mathbf{T}$ (the number of test cases or games). 

The $\mathbf{T}$ subsequent lines each contain an integer, $N$ (the number of blocks for that test case).

Constraints 

$1\leq T\leq100$

$1\leq N\leq10^5$

Output Format

For each test case, print the name of the winner (i.e.: either Kitty or Katty) on a new line.

Sample Input
2
2
3

Sample Output
Kitty
Katty

Explanation

Test Case 0: 

$N=2$ so there are two blocks labeled $\mbox{1}$ and $2$. Kitty chooses $A=2$ and $B=1$, then inserts a new block with  the label $\mbox{1}$ (the result of $2-1$). The game ends, as there is now only $\mbox{I}$ block in the set. The label on the last block, $\mbox{X}$, is $\mbox{1}$, so we calculate $result=1\%3=1$. Because  $result=1$, Kitty wins and we print Kitty on a new line.

Test Case 1: 

$N=3$, so there are three blocks labeled $\mbox{1}$, $2$, and $3$. No matter how Kitty makes the first move, Katty will win. If Kitty chooses $A=3$ and $B=2$ on the first move and inserts a block labeled $\mbox{I}$ (the result of $3-2$), the set of blocks becomes $\{1,1\}$. Katty then must choose $A=1$ and $B=1$ and insert a new block labeled $\mbox{o}$ (the result of $1-1$). The game ends, as there is now only $\mbox{I}$ block in the set. The label on the last block, $\mbox{X}$, is $\mbox{0}$, so we calculate $result=0\%3=0$. Because $result=0$ and Katty made the last move, Katty wins and we print Katty on a new line.

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
To celebrate the opening of the Winter Computer School the organizers decided to buy in *n* liters of cola. However, an unexpected difficulty occurred in the shop: it turned out that cola is sold in bottles 0.5, 1 and 2 liters in volume. At that, there are exactly *a* bottles 0.5 in volume, *b* one-liter bottles and *c* of two-liter ones. The organizers have enough money to buy any amount of cola. What did cause the heated arguments was how many bottles of every kind to buy, as this question is pivotal for the distribution of cola among the participants (and organizers as well).

Thus, while the organizers are having the argument, discussing different variants of buying cola, the Winter School can't start. Your task is to count the number of all the possible ways to buy exactly *n* liters of cola and persuade the organizers that this number is too large, and if they keep on arguing, then the Winter Computer School will have to be organized in summer.

All the bottles of cola are considered indistinguishable, i.e. two variants of buying are different from each other only if they differ in the number of bottles of at least one kind.

Input Specification:
The first line contains four integers — *n*, *a*, *b*, *c* (1<=≤<=*n*<=≤<=10000, 0<=≤<=*a*,<=*b*,<=*c*<=≤<=5000).

Output Specification:
Print the unique number — the solution to the problem. If it is impossible to buy exactly *n* liters of cola, print 0.

Demo Input:
['10 5 5 5\n', '3 0 0 2\n']

Demo Output:
['9\n', '0\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a non-negative integer num, return the number of steps to reduce it to zero. If the current number is even, you have to divide it by 2, otherwise, you have to subtract 1 from it.
 
Example 1:
Input: num = 14
Output: 6
Explanation: 
Step 1) 14 is even; divide by 2 and obtain 7. 
Step 2) 7 is odd; subtract 1 and obtain 6.
Step 3) 6 is even; divide by 2 and obtain 3. 
Step 4) 3 is odd; subtract 1 and obtain 2. 
Step 5) 2 is even; divide by 2 and obtain 1. 
Step 6) 1 is odd; subtract 1 and obtain 0.

Example 2:
Input: num = 8
Output: 4
Explanation: 
Step 1) 8 is even; divide by 2 and obtain 4. 
Step 2) 4 is even; divide by 2 and obtain 2. 
Step 3) 2 is even; divide by 2 and obtain 1. 
Step 4) 1 is odd; subtract 1 and obtain 0.

Example 3:
Input: num = 123
Output: 12

 
Constraints:

0 <= num <= 10^6

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Our Chef is doing what he is best at, COOKING A BARBECUE for his guests. He has invited all of us, and taking the help of his apprentice to smoke the barbecues. The chef has got BBQ sticks, each can take N fillings, and he presents N distinctly filled sticks in front his guests forming a N*N  matrix

But here is the problem, he has got only two type of fillings, meat and capsicum, but still wants the N  sticks to look "presentable", he is very particular about it. As a solution he fills the main diagonal of the N*N  matrix with the same type of filling (either meat or capsicum) forming a "presentable" set

The Chef's apprentice is a fool, so the Chef asks him to cook M distinctly filled sticks ,so that the Chef is sure that among M there exist N sticks forming a "presentable" set. Your job is to determine smallest possible value of M.


-----Input-----
T, the number of test cases, followed by T lines. 
Each line containing the positive integer N >= 4

-----Output-----
T lines of output, each line contain the positive integer M

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

Output:
5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alice, Bob and Charlie are bidding for an artifact at an auction.  
Alice bids A rupees, Bob bids B rupees, and Charlie bids C rupees (where A, B, and C are distinct). 

According to the rules of the auction, the person who bids the highest amount will win the auction.  
Determine who will win the auction.

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

- The first line contains a single integer T — the number of test cases. Then the test cases follow.
- The first and only line of each test case contains three integers A, B, and C, — the amount bid by Alice, Bob, and Charlie respectively.

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

For each test case, output who (out of Alice, Bob, and Charlie) will win the auction.

You may print each character of Alice, Bob, and Charlie in uppercase or lowercase (for example, ALICE, aliCe, aLIcE will be considered identical).

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

$1 ≤ T ≤ 1000$
$1 ≤ A, B, C ≤ 1000$
$A$, $B$, and $C$ are distinct.

----- Sample Input 1 ------ 
4
200 100 400
155 1000 566
736 234 470
124 67 2

----- Sample Output 1 ------ 
Charlie
Bob
Alice
Alice

----- explanation 1 ------ 
Test Case $1$: Charlie wins the auction since he bid the highest amount.

Test Case $2$: Bob wins the auction since he bid the highest amount.

Test Case $3$: Alice wins the auction since she bid the highest amount.

Test Case $4$: Alice wins the auction since she bid the highest amount.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We call an quadruple of positive integers, $(W,X,Y,Z)$, beautiful if the following condition is true:

$W\oplus X\oplus Y\oplus Z\neq0$

Note: $\theta$ is the bitwise XOR operator.

Given $\mbox{A}$, $\mbox{B}$, $\mbox{C}$, and $\mbox{D}$, count the number of beautiful quadruples of the form $(W,X,Y,Z)$ where the following constraints hold:

$1\leq W\leq A$
$1\leq X\leq B$
$1\leq Y\leq C$
$1\leq z\leq D$

When you count the number of beautiful quadruples, you should consider two quadruples as same if the following are true:

They contain same integers.
Number of times each integers occur in the quadruple is same.

For example $(1,1,1,2)$ and $(1,1,2,1)$ should be considered as same.

Input Format

A single line with four space-separated integers describing the respective values of $\mbox{A}$, $\mbox{B}$, $\mbox{C}$, and $\mbox{D}$.

Constraints

$1\leq A,B,C,D\leq3000$
For $50\%$ of the maximum score, $1\leq A,B,C,D\leq50$

Output Format

Print the number of beautiful quadruples.

Sample Input
1 2 3 4

Sample Output
11

Explanation

There are $\mbox{11}$ beautiful quadruples for this input:

$(1,1,1,2)$
$(1,1,1,3)$
$(1,1,1,4)$
$(1,1,2,3)$
$(1,1,2,4)$
$(1,1,3,4)$
$(1,2,2,2)$
$(1,2,2,3)$
$(1,2,2,4)$
$(1,2,3,3)$
$(1,2,3,4)$

Thus, we print $\mbox{11}$ as our output.

Note that $(1,1,1,2)$ is same as $(1,1,2,1)$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are an eccentric billionaire with an affinity for sending stuff to Mars. In an ideal world you would send stuff to Mars all the time, but your engineers tell you that it is most efficient to do it when Earth and Mars are somewhat close to each other. 

Your engineers have calculated that optimal launch windows occur once every 26 months, and that one of them occurs in April 2018. They also tell you that they will not have any Big Finished Rockets by then, so you will have to wait for a later launch window.

Since your rocket scientists apparently can not be bothered to tell you about the optimal launch windows before it is too late, you have to keep track of that yourself. Write a program that determines if there is an optimal launch window in any given year.

-----Input-----
The only line of input contains an integer $y$ ($2018 \le y \le 10000$), the year you are interested in.

-----Output-----
Output “yes” if there is an optimal launch window in the year $y$, otherwise output “no”.

-----Examples-----
Sample Input 1:
2018
Sample Output 1:
yes

Sample Input 2:
2019
Sample Output 2:
no

Sample Input 3:
2020
Sample Output 3:
yes

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Maria plays college basketball and wants to go pro.  Each season she maintains a record of her play.  She tabulates the number of times she breaks her season record for most points and least points in a game.  Points scored in the first game establish her record for the season, and she begins counting from there.

Example 

$scores=[12,24,10,24]$   

Scores are in the same order as the games played.  She tabulates her results as follows:

                                     Count
    Game  Score  Minimum  Maximum   Min Max
     0      12     12       12       0   0
     1      24     12       24       0   1
     2      10     10       24       1   1
     3      24     10       24       1   1

Given the scores for a season, determine the number of times Maria breaks her records for most and least points scored during the season.

Function Description  

Complete the breakingRecords function in the editor below. 

breakingRecords has the following parameter(s):  

int scores[n]: points scored per game   

Returns   

int[2]: An array with the numbers of times she broke her records. Index $0$ is for breaking most points records, and index $1$ is for breaking least points records.  

Input Format

The first line contains an integer $n$, the number of games. 

The second line contains $n$ space-separated integers describing the respective values of $score_0,score_1,...,score_{n-1}$.

Constraints

$1\leq n\leq1000$
$0\leq scores[i]\leq10^8$

Sample Input 0
9
10 5 20 20 4 5 2 25 1

Sample Output 0
2 4

Explanation 0

The diagram below depicts the number of times Maria broke her best and worst records throughout the season:

She broke her best record twice (after games $2$ and $7$) and her worst record four times (after games $1$, $4$, $\boldsymbol{6}$, and $8$), so we print 2 4 as our answer. Note that she did not break her record for best score during game $3$, as her score during that game was not strictly greater than her best record at the time.

Sample Input 1
10
3 4 21 36 10 28 35 5 24 42

Sample Output 1
4 0

Explanation 1

The diagram below depicts the number of times Maria broke her best and worst records throughout the season:

She broke her best record four times (after games $1$, $2$, $3$, and $\mbox{9}$) and her worst record zero times (no score during the season was lower than the one she earned during her first game), so we print 4 0 as our answer.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
After lessons Nastya decided to read a book. The book contains $n$ chapters, going one after another, so that one page of the book belongs to exactly one chapter and each chapter contains at least one page.

Yesterday evening Nastya did not manage to finish reading the book, so she marked the page with number $k$ as the first page which was not read (i.e. she read all pages from the $1$-st to the $(k-1)$-th).

The next day Nastya's friend Igor came and asked her, how many chapters remain to be read by Nastya? Nastya is too busy now, so she asks you to compute the number of chapters she has not completely read yet (i.e. the number of chapters she has not started to read or has finished reading somewhere in the middle).


-----Input-----

The first line contains a single integer $n$ ($1 \leq n \leq 100$) — the number of chapters in the book.

There are $n$ lines then. The $i$-th of these lines contains two integers $l_i$, $r_i$ separated by space ($l_1 = 1$, $l_i \leq r_i$) — numbers of the first and the last pages of the $i$-th chapter. It's guaranteed that $l_{i+1} = r_i + 1$ for all $1 \leq i \leq n-1$, and also that every chapter contains at most $100$ pages.

The $(n+2)$-th line contains a single integer $k$ ($1 \leq k \leq r_n$) — the index of the marked page. 


-----Output-----

Print a single integer — the number of chapters which has not been completely read so far.


-----Examples-----
Input
3
1 3
4 7
8 11
2

Output
3

Input
3
1 4
5 9
10 12
9

Output
2

Input
1
1 7
4

Output
1



-----Note-----

In the first example the book contains $11$ pages and $3$ chapters — $[1;3]$, $[4;7]$ and $[8;11]$. Nastya marked the $2$-nd page, so she finished in the middle of the $1$-st chapter. So, all chapters has not been read so far, so the answer is $3$.

The book in the second example contains $12$ pages and $3$ chapters too, but Nastya finished reading in the middle of the $2$-nd chapter, so that the answer is $2$.

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