vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Beru-taxi

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Vasiliy lives at point (*a*,<=*b*) of the coordinate plane. He is hurrying up to work so he wants to get out of his house as soon as possible. New app suggested *n* available Beru-taxi nearby. The *i*-th taxi is located at point (*x**i*,<=*y**i*) and moves with a speed *v**i*. 

Consider that each of *n* drivers will move directly to Vasiliy and with a maximum possible speed. Compute the minimum time when Vasiliy will get in any of Beru-taxi cars.

Input Specification:
The first line of the input contains two integers *a* and *b* (<=-<=100<=≤<=*a*,<=*b*<=≤<=100) — coordinates of Vasiliy's home.

The second line contains a single integer *n* (1<=≤<=*n*<=≤<=1000) — the number of available Beru-taxi cars nearby. 

The *i*-th of the following *n* lines contains three integers *x**i*, *y**i* and *v**i* (<=-<=100<=≤<=*x**i*,<=*y**i*<=≤<=100, 1<=≤<=*v**i*<=≤<=100) — the coordinates of the *i*-th car and its speed.

It's allowed that several cars are located at the same point. Also, cars may be located at exactly the same point where Vasiliy lives.

Output Specification:
Print a single real value — the minimum time Vasiliy needs to get in any of the Beru-taxi cars. You answer will be considered correct if its absolute or relative error does not exceed 10<=-<=6. 

Namely: let's assume that your answer is *a*, and the answer of the jury is *b*. The checker program will consider your answer correct, if .

Demo Input:
['0 0\n2\n2 0 1\n0 2 2\n', '1 3\n3\n3 3 2\n-2 3 6\n-2 7 10\n']

Demo Output:
['1.00000000000000000000', '0.50000000000000000000']

Note:
In the first sample, first taxi will get to Vasiliy in time 2, and second will do this in time 1, therefore 1 is the answer.

In the second sample, cars 2 and 3 will arrive simultaneously.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Rahul is a serial killer. Rahul has been betrayed by his lover in the past and now he want to eliminate entire Universe.He has already Eliminated majority of the population and now only a handful number of people are left. Like other Serial killers, he has an interesting pattern of killing people. 
He either kill one individual at a time or if he find two individuals of different heights,he eliminates both of them simultaneously. Now Rahul wants to eliminate them as quickly as he can.
So given $N$ as the number of people left and an array containing height of those $N$ people,tell the minimum number of kills Rahul require to eliminate the entire universe.

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- Each test case constitutes of Two lines. 
- First line contains $N$, representing the number of people left in the universe
- The second line contains an array $a[i]$ of size $N$ containing heights of those $N$ people.

-----Output:-----
For each testcase, you have to output a Single line Containing the minimum number of kills required by Rahul to eliminate the Universe.

-----Constraints-----
- $1 \leq T \leq 50000$
- $1 \leq N \leq 50000$
- $100 \leq a[i] \leq 10^5$

-----Sample Input:-----
1
10
178 184 178 177 171 173 171 183 171 175

-----Sample Output:-----
5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a pizza with 3n slices of varying size, you and your friends will take slices of pizza as follows:

You will pick any pizza slice.
Your friend Alice will pick next slice in anti clockwise direction of your pick. 
Your friend Bob will pick next slice in clockwise direction of your pick.
Repeat until there are no more slices of pizzas.

Sizes of Pizza slices is represented by circular array slices in clockwise direction.
Return the maximum possible sum of slice sizes which you can have.
 
Example 1:

Input: slices = [1,2,3,4,5,6]
Output: 10
Explanation: Pick pizza slice of size 4, Alice and Bob will pick slices with size 3 and 5 respectively. Then Pick slices with size 6, finally Alice and Bob will pick slice of size 2 and 1 respectively. Total = 4 + 6.

Example 2:

Input: slices = [8,9,8,6,1,1]
Output: 16
Output: Pick pizza slice of size 8 in each turn. If you pick slice with size 9 your partners will pick slices of size 8.

Example 3:
Input: slices = [4,1,2,5,8,3,1,9,7]
Output: 21

Example 4:
Input: slices = [3,1,2]
Output: 3

 
Constraints:

1 <= slices.length <= 500
slices.length % 3 == 0
1 <= slices[i] <= 1000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Salt and Pepper has decided to survey all the restaurants from the city to know which of them are its allies and which of them are its enemies. They have given this task to the bright residents of our G-Wing!
Note that any two restaurants can either be allies or rivals or neutral.
There are N restaurants in Gandhinagar numbered from 0 to N-1. There are four types of queries which you have to answer for given two restaurants x and y:-

Q = 1
Answer whether restaurant x and y are allies or not by printing YES or NO.

Q = 2
Answer whether restaurant x and y are rivals or not by printing YES or NO.

Q = 3
Make restaurant x and y allies. If they are already enemies print -1 and do nothing.

Q = 4
Make restaurant x and y rivals. If they are already allies print -1 and do nothing.

Ally and Rivalry are both mutual (Eg. if a is ally with b, then b is also ally with a). 

Each restaurant is ally of itself and no restaurant is rival of itself.

Assume there are 3 restaurants a, b, c

If a is ally with b and b is ally with c, then a is also ally with c.

If a is ally with b and b is rival with c, then a is also rival with c. (Rival of ally is your rival).

If a is rival with b and b is rival with c, then a is ally with c. (Rival of rival is your ally).

Input :

First line will contain N and T denoting the number of restaurants and number of queries respectively.
Each of the next T lines will contain three integers Q q w denoting the query type mentioned above, restaurants q and w respectively.

Output :

Answer the queries as mentioned above. 

Constrains :

2 ≤ N, T ≤ 1000000

1 ≤ Q ≤ 4

0 ≤ q,w < N

Author : Manish Berwani

SAMPLE INPUT
8 8
3 1 2
3 2 5
3 3 4
4 1 5
4 2 6
1 1 5
2 2 3
1 2 6

SAMPLE OUTPUT
-1
YES
NO
NO

Explanation

First Query makes 1 and 2 allies.

Second Query makes 2 and 5 allies.

Third Query makes 3 and 4 allies.

Fourth Query tries to make 1 and 5 enemy, but they are already friends. So it prints -1.

Fifth Query makes 2 and 6 rivals.

Sixth Query:- 1 and 5 are allies so YES

Seventh Query:- 2 and 3 are not rivals so NO

Eighth Query:- 2 and 6 are rivals and not allies so NO

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarp is a big lover of killing time in social networks. A page with a chatlist in his favourite network is made so that when a message is sent to some friend, his friend's chat rises to the very top of the page. The relative order of the other chats doesn't change. If there was no chat with this friend before, then a new chat is simply inserted to the top of the list.

Assuming that the chat list is initially empty, given the sequence of Polycaprus' messages make a list of chats after all of his messages are processed. Assume that no friend wrote any message to Polycarpus.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 200 000) — the number of Polycarpus' messages. Next n lines enlist the message recipients in the order in which the messages were sent. The name of each participant is a non-empty sequence of lowercase English letters of length at most 10.


-----Output-----

Print all the recipients to who Polycarp talked to in the order of chats with them, from top to bottom.


-----Examples-----
Input
4
alex
ivan
roman
ivan

Output
ivan
roman
alex

Input
8
alina
maria
ekaterina
darya
darya
ekaterina
maria
alina

Output
alina
maria
ekaterina
darya



-----Note-----

In the first test case Polycarpus first writes to friend by name "alex", and the list looks as follows:   alex 

Then Polycarpus writes to friend by name "ivan" and the list looks as follows:  ivan  alex 

Polycarpus writes the third message to friend by name "roman" and the list looks as follows:  roman  ivan  alex 

Polycarpus writes the fourth message to friend by name "ivan", to who he has already sent a message, so the list of chats changes as follows:  ivan  roman  alex

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
John gave Jack a very hard problem. He wrote a very big positive integer A0 on a piece of paper. The number is less than 10200000 . In each step, Jack is allowed to put ' + ' signs in between some of the digits (maybe none) of the current number and calculate the sum of the expression. He can perform the same procedure on that sum and so on. The resulting sums can be labeled respectively by A1, A2 etc. His task is to get to a single digit number.

The problem is that there is not much blank space on the paper. There are only three lines of space, so he can't perform more than three steps. Since he wants to fill up the paper completely, he will perform exactly three steps.

Jack must not add leading zeros to intermediate results, but he can put ' + ' signs in front of digit 0. For example, if the current number is 1000100, 10 + 001 + 00 is a valid step, resulting in number 11.

Input

First line contains a positive integer N (1 ≤ N ≤ 200000), representing the number of digits of A0.

Second line contains a string of length N representing positive integer number A0. Each character is digit. There will be no leading zeros.

Output

Output exactly three lines, the steps Jack needs to perform to solve the problem. You can output any sequence of steps which results in a single digit number (and is logically consistent).

Every step consists of digits and ' + ' signs. Steps should not contain several ' + ' signs in a row, whitespaces, or ' + ' signs as the first or last character. They also need to be arithmetically consistent.

Solution might not be unique. Output any of them in that case.

Examples

Input

1
1


Output

1
1
1


Input

4
5806


Output

5+8+0+6
1+9
1+0

Note

In the first sample, Jack can't put ' + ' signs anywhere, so he just writes 1 in each line and solves the problem. Here, solution is unique.

In the second sample, Jack first puts ' + ' between every two consecutive digits, thus getting the result 5 + 8 + 0 + 6 = 19. He does the same on the second step, getting 1 + 9 = 10. Once more, he gets 1 + 0 = 1, so after three steps, the result is 1 and his solution is correct.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Read problems statements [Hindi] , [Vietnamese] , [Mandarin Chinese] , [Russian] and [Bengali] as well.

You are given a directed acyclic graph with $N$ vertices (numbered $1$ through $N$) and $M$ edges. You want to destroy it all! To destroy the graph, you should delete all of its vertices. 

In one step, you are allowed to delete at most two vertices; you may only delete a vertex when there is no edge from it to another (not yet deleted) vertex. You may not delete two vertices when there is an edge between them either.

Find a way to destroy the graph in the minimum number of steps.

------  Input ------
The first line of the input contains two space-separated integers $N$ and $M$.
Each of the next $M$ lines contains two space-separated integers $U$ and $V$ denoting an edge from vertex $U$ to vertex $V$.

------  Output ------
The first line of the output should contain a single integer $S$ denoting the minimum number of steps needed to destroy the graph.
Each of the next $S$ lines should describe one step; it should contain an integer $K$ ($1 ≤ K ≤ 2$), followed by a space and $K$ space-separated integers denoting the numbers of vertices deleted in this step.

------  Constraints  ------
$1 ≤ N, M ≤ 10^{6}$
the graph on the input does not contain any cycles or self-loops

------  Scoring ------
The score for each test file is $10 \cdot (C/S)^2$, where $C$ is the number of steps in which you deleted exactly $2$ vertices. The final score of your submission is equal to the sum of scores for each test file.

There are twenty test cases. During the contest, the displayed score will account for exactly four test files, i.e. your score reflects your submission's performance on 20% (4/20) of the test files. However, if your program gets a non-AC verdict on any test file, your submission's verdict will be non-AC. In other words, an AC verdict denotes that your program runs successfully on all the test files. After the end of the contest, your score will be changed to include the sum of your program's scores over the other sixteen test files.

------  Example Input ------

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

------  Example Output ------

4
2 4 5
2 6 3
1 2
1 1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a girl named ''Akansha''. She is very fond of eating chocolates but she has a weak immune system due to which she gets cold after eating chocolate during morning, evening and night and can only eat at most $x$ number of chocolate each afternoon. A friend of hers gifted her some $n$ number of chocolates that she doesn't want to share with anyone. Those chocolate have to be finished before they expire. (no. of days in which they are going to expire from the day she has been gifted the chocolate is given for each chocolate)   $Note:$ Chocolate cannot be consumed on the day it expires.

Help Akansha to know if it is possible for her to finish all the chocolates before they expire or not.

-----Input:-----
- First line will contain $T$, number of test cases. Then the test cases follow. 
- First line contains $n$,the number of chocolates gifted to her
- Second line contains $x$,the number of chocolates she can eat each afternoon
- Third line contains $n$ space separated integers $A1,A2...An$,denoting the expiry of each of the $n$ chocolates

-----Output:-----
For each testcase, print $Possible$, if she can complete all the chocolates gifted to her. Otherwise, print $Impossible$, if she can not finish all the chocolates.

-----Constraints-----
- $1 \leq T \leq 100$
- $1 \leq n \leq 1500$
- $1 \leq x \leq 1500$
- $1 \leq Ai \leq 1500$

-----Subtasks-----
- 100 points : $Original Constraints$

-----Sample Input:-----
3

3

5

4 1 2

5

2

4 4 3 2 2

5

1

4 2 3 1 1   

-----Sample Output:-----
Impossible

Possible

Impossible   

-----EXPLANATION:-----
- 
Example case 1

1st and 3rd chocolate on the 1st afternoon as she can consume at most 5. one chocolate will be wasted.
$Note:$ she cannot eat the 2nd chocolate because chocolates cannot be consumed on the day of expiry.
- 
Example case 2

4th and 5th chocolate on 1st afternoon, 3rd and 1st chocolate on 2nd afternoon. And 2nd chocolate on the 3rd afternoon.
It will take a total of 3 days to finish the chocolate.
- 
Example case 3

She cannot eat 4th and 5th chocolate as they will expire on the very 1st day, she can eat 2nd chocolate on 1st afternoon, then 3rd chocolate on 2nd afternoon, then 1st chocolate on 3rd afternoon, and 2 chocolates 4th and 5th will expire.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You will be given a string. 

You need to return an array of three strings by gradually pulling apart the string.

You should repeat the following steps until the string length is 1:

a) remove the final character from the original string, add to solution string 1.
b) remove the first character from the original string, add to solution string 2.

The final solution string value is made up of the remaining character from the original string, once originalstring.length == 1.

Example:

"exampletesthere"
becomes:
["erehtse","example","t"]

The Kata title gives a hint of one technique to solve.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In a country popular for train travel, you have planned some train travelling one year in advance.  The days of the year that you will travel is given as an array days.  Each day is an integer from 1 to 365.
Train tickets are sold in 3 different ways:

a 1-day pass is sold for costs[0] dollars;
a 7-day pass is sold for costs[1] dollars;
a 30-day pass is sold for costs[2] dollars.

The passes allow that many days of consecutive travel.  For example, if we get a 7-day pass on day 2, then we can travel for 7 days: day 2, 3, 4, 5, 6, 7, and 8.
Return the minimum number of dollars you need to travel every day in the given list of days.
 
Example 1:
Input: days = [1,4,6,7,8,20], costs = [2,7,15]
Output: 11
Explanation: 
For example, here is one way to buy passes that lets you travel your travel plan:
On day 1, you bought a 1-day pass for costs[0] = $2, which covered day 1.
On day 3, you bought a 7-day pass for costs[1] = $7, which covered days 3, 4, ..., 9.
On day 20, you bought a 1-day pass for costs[0] = $2, which covered day 20.
In total you spent $11 and covered all the days of your travel.


Example 2:
Input: days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]
Output: 17
Explanation: 
For example, here is one way to buy passes that lets you travel your travel plan:
On day 1, you bought a 30-day pass for costs[2] = $15 which covered days 1, 2, ..., 30.
On day 31, you bought a 1-day pass for costs[0] = $2 which covered day 31.
In total you spent $17 and covered all the days of your travel.

 

Note:

1 <= days.length <= 365
1 <= days[i] <= 365
days is in strictly increasing order.
costs.length == 3
1 <= costs[i] <= 1000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
One of the main tasks of an operating system is process scheduling, i.e., managing CPU sharing among a community of ready processes. Several algorithms exist for scheduling tasks to the CPU. Here we are considering Round Robin Scheduling(in a single CPU system) which is the most widely used of all the scheduling algorithms.

Round Robin works with a timer interrupt which is set to occur after specific time intervals.
Suppose there are n processes which need the CPU. Each process has a specific run time(amount of CPU time it needs to complete the process). 
Initially CPU is allocated to the first process. It stays on CPU till the timer interrupt occurs or till the process is complete, whichever happens first. Then CPU is allocated to the next task, which stays there till the next timer interrupt. This goes on till all n tasks get the CPU. After all n tasks the cycle is repeated again. This continues till all the processes are over.

Your task is to answer queries of two kind as described in input section.

Input:

First line contains two integers N (1 ≤ N ≤ 100000), the no. of processes and C (1 ≤ C ≤ 10000), cycle length(interval after which each interrupt occurs).

The next line contains N integers, with ith line containing the run time of process indexed i(1 ≤ A[i] ≤ 1000000000). Indexing is 1-based.

The next line contains integer Q (1 ≤ Q ≤ 100000), denoting the number of queries on this data.
Each of the next Q lines contain two space-separated integers M (1 or 2) and D (1 ≤ D ≤ N).
M indicates the mode of query.

1) 1 D
2) 2 D

where:
M=1, for wait time of process D, i.e., how much time it has to wait before getting CPU for the first time.

M=2, for rank of process D when finished, e.g., if process D is 5th to get completed, then output 5.

Output:

There should be one line of input for each query.

If M=1, output the wait time of each process, which is the time from the start till the process with index D first gets the CPU.

If M=2, output an integer k, where process D was the kth process to get finished(see sample input for a better understanding).
Register for IndiaHacksSAMPLE INPUT
5 5
10 7 3 15 9
10
1 1
1 2
1 3
1 4
1 5
2 1
2 2
2 3
2 4
2 5

SAMPLE OUTPUT
0
5
10
13
18
2
3
1
5
4

Register for IndiaHacks

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Walter White and Jesse Pinkman have now established their bases at different places.  
Now they want to form a network, that is, they want that all their bases should be reachable from every base. 
One base is reachable from other base if there is a path of tunnels connecting bases.  
Bases are suppose based on a 2-D plane having integer coordinates.   
Cost of building tunnels between two bases are coordinates (x1,y1) and (x2,y2) is min{ |x1-x2|, |y1-y2| }.  

What is the minimum cost such that a network is formed.   

Input: 
First line contains N, the number of bases.  
Each of the next N lines contain two integers xi and yi.

Output: 
Print the minimum cost of building the network.

Constraints: 
1 ≤ N ≤ 100000  
-10^9 ≤ xi,yi ≤ 10^9

SAMPLE INPUT
2
1 5
7 8

SAMPLE OUTPUT
3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given is a number sequence A of length N.
Find the number of integers i \left(1 \leq i \leq N\right) with the following property:
 - For every integer j \left(1 \leq j \leq N\right) such that i \neq j , A_j does not divide A_i.

-----Constraints-----
 - All values in input are integers.
 - 1 \leq N \leq 2 \times 10^5
 - 1 \leq A_i \leq 10^6

-----Input-----
Input is given from Standard Input in the following format:
N
A_1 A_2 \cdots A_N

-----Output-----
Print the answer.

-----Sample Input-----
5
24 11 8 3 16

-----Sample Output-----
3

The integers with the property are 2, 3, and 4.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given are three positive integers A, B, and C. Compute the following value modulo 998244353:
\sum_{a=1}^{A} \sum_{b=1}^{B} \sum_{c=1}^{C} abc

-----Constraints-----
 - 1 \leq A, B, C \leq 10^9

-----Input-----
Input is given from standard input in the following format:
A B C

-----Output-----
Print the value modulo 998244353.

-----Sample Input-----
1 2 3

-----Sample Output-----
18

We have: (1 \times 1 \times 1) + (1 \times 1 \times 2) + (1 \times 1 \times 3) + (1 \times 2 \times 1) + (1 \times 2 \times 2) + (1 \times 2 \times 3) = 1 + 2 + 3 + 2 + 4 + 6 = 18.

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