vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Rhezo has just joined HackerEarth as an intern. Like most companies, HackerEarth too has a lot of computers and some departments. For efficient communication, it is very important that every computer can connect with each other in the same department, with the connection not being necessarily direct. 

When each computer can connect with any other computer in the same department, that department is said to be happy. Initially all departments are happy.

Rhezo's friend Lonewolf wants to have some fun, and will cut some connection between any two computers for Q days. You being the Happy Manager of HackerEarth, need to tell for each of the Q days, if some department becomes unhappy.

Input:

First line contains 2 integers N and M, denoting the number of computers and number of wire connections at HackerEarth. Each of the next M lines contain 2 integers A_i and B_i, meaning that computer number A_i is connected to computer number B_i. 

Next line contains an integer Q, denoting the number of days Lonewolf cuts a connection between 2 computers at HackerEarth. Each of the next Q lines contain a single integer P, which means that connection between computer A_p and computer B_p is cut.

Output:

For each of the Q days, you need to tell whether any department is unhappy or not. If all departments are happy, print "Happy"(without quotes), else print "Unhappy"(without quotes).

Constraints:

1 ≤ N ,M ≤ 10^{5} 

1 ≤ A_i, B_i ≤ N

1 ≤ P ≤ M

1 ≤ M ≤ max(10^{5},N \cdot (N-1) / 2)

SAMPLE INPUT
5 5
1 2
2 3
3 4
4 5
3 5
5
1
2
3
4
5

SAMPLE OUTPUT
Unhappy
Unhappy
Happy
Happy
Happy

Explanation

For the 3^{rd} query, when we delete the connection between computer 3 and computer 4, these two computers can still connect via this connection : 3 \rightarrow 5 \rightarrow 4.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are preparing for an exam on scheduling theory. The exam will last for exactly T milliseconds and will consist of n problems. You can either solve problem i in exactly t_{i} milliseconds or ignore it and spend no time. You don't need time to rest after solving a problem, either.

Unfortunately, your teacher considers some of the problems too easy for you. Thus, he assigned an integer a_{i} to every problem i meaning that the problem i can bring you a point to the final score only in case you have solved no more than a_{i} problems overall (including problem i).

Formally, suppose you solve problems p_1, p_2, ..., p_{k} during the exam. Then, your final score s will be equal to the number of values of j between 1 and k such that k ≤ a_{p}_{j}.

You have guessed that the real first problem of the exam is already in front of you. Therefore, you want to choose a set of problems to solve during the exam maximizing your final score in advance. Don't forget that the exam is limited in time, and you must have enough time to solve all chosen problems. If there exist different sets of problems leading to the maximum final score, any of them will do.


-----Input-----

The first line contains two integers n and T (1 ≤ n ≤ 2·10^5; 1 ≤ T ≤ 10^9) — the number of problems in the exam and the length of the exam in milliseconds, respectively.

Each of the next n lines contains two integers a_{i} and t_{i} (1 ≤ a_{i} ≤ n; 1 ≤ t_{i} ≤ 10^4). The problems are numbered from 1 to n.


-----Output-----

In the first line, output a single integer s — your maximum possible final score.

In the second line, output a single integer k (0 ≤ k ≤ n) — the number of problems you should solve.

In the third line, output k distinct integers p_1, p_2, ..., p_{k} (1 ≤ p_{i} ≤ n) — the indexes of problems you should solve, in any order.

If there are several optimal sets of problems, you may output any of them.


-----Examples-----
Input
5 300
3 100
4 150
4 80
2 90
2 300

Output
2
3
3 1 4

Input
2 100
1 787
2 788

Output
0
0


Input
2 100
2 42
2 58

Output
2
2
1 2



-----Note-----

In the first example, you should solve problems 3, 1, and 4. In this case you'll spend 80 + 100 + 90 = 270 milliseconds, falling within the length of the exam, 300 milliseconds (and even leaving yourself 30 milliseconds to have a rest). Problems 3 and 1 will bring you a point each, while problem 4 won't. You'll score two points.

In the second example, the length of the exam is catastrophically not enough to solve even a single problem.

In the third example, you have just enough time to solve both problems in 42 + 58 = 100 milliseconds and hand your solutions to the teacher with a smile.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Right now you are to solve a very, very simple problem — to crack the safe. Four positive integers stand one by one on a circle protecting the safe. You know that to unlock this striking safe you have to make all four numbers equal to one. Operations are as follows: you may choose two adjacent numbers and increase both by one; you may choose two adjacent even numbers and divide both by two. Nothing else. Crack the safe!

Input

The single line of the input contains four space-separated integer positive numbers not greater than 109 each — four numbers on the circle in consecutive order.

Output

The output should contain "-1" (quotes for clarity) if the safe is secure, that is it's impossible to crack it. Otherwise, output should contain the sequence of operations (one operations per line) leading to unlocking the safe. You don't have to minimize the number of operations, but it should not exceed 1000. To make things clear, assume numbers stand on positions 1 through 4. Each operation is encoded by two symbols. If the following operation is dividing then first symbol is '/'; otherwise it's '+' (addition). The second symbol is the position of the first number in pair in consecutive order. (see samples for clarification).

If there are several solutions, output any of them.

Examples

Input

1 1 1 1


Output



Input

1 2 4 2


Output

/2
/3


Input

3 3 1 1


Output

+1
/1
/1


Input

2 1 2 4


Output

/3
/4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
-----Problem Statement-----
Write a program that accepts a number, n, and outputs the same.

-----Input-----
The only line contains a single integer. 

-----Output-----
Output the answer in a single line.

-----Constraints-----
- 0 ≤ n ≤ 105

-----Sample Input-----
123

-----Sample Output-----
123

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Oliver and Bob are best friends. They have spent their entire childhood in the beautiful city of Byteland. The people of Byteland live happily along with the King.
The city has a unique architecture with total N houses. The King's Mansion is a very big and beautiful bungalow having address = 1. Rest of the houses in Byteland have some unique address, (say A), are connected by roads and  there is always a unique path between any two houses in the city. Note that the King's Mansion is also included in these houses.

Oliver and Bob have decided to play Hide and Seek taking the entire city as their arena. In the given scenario of the game, it's Oliver's turn to hide and Bob is supposed to find him.
Oliver can hide in any of the houses in the city including the King's Mansion. As Bob is a very lazy person, for finding Oliver, he either goes towards the King's Mansion (he stops when he reaches there), or he moves away from the Mansion in any possible path till the last house on that path.

Oliver runs and hides in some house (say X) and Bob is starting the game from his house (say Y). If Bob reaches house X, then he surely finds Oliver.

Given Q queries, you need to tell Bob if it is possible for him to find Oliver or not.

The queries can be of the following two types:
0 X Y : Bob moves towards the King's Mansion.
1 X Y : Bob moves away from the King's Mansion

INPUT :
The first line of the input contains a single integer N, total number of houses in the city. 
Next N-1 lines contain two space separated integers A and B denoting a road between the houses at address A and B.
Next line contains a single integer Q denoting the number of queries.
Following Q lines contain three space separated integers representing each query as explained above.

OUTPUT :
Print "YES" or "NO" for each query depending on the answer to that query.

CONSTRAINTS :
1 ≤ N ≤ 10^5
1 ≤ A,B ≤ N
1 ≤ Q ≤ 5*10^5
1 ≤ X,Y ≤ N

NOTE :
Large Input size. Use printf scanf or other fast I/O methods.

SAMPLE INPUT
9
1 2
1 3
2 6
2 7
6 9
7 8
3 4
3 5
5
0 2 8
1 2 8
1 6 5
0 6 5
1 9 1

SAMPLE OUTPUT
YES
NO
NO
NO
YES

Explanation

Query 1
Bob goes from 8 towards 1 meeting 2 in the path.
Query 2
Bob goes from 8 away from 1 and never meets 2.
Query 3
Bob goes from 5 away from 1 and never meets 6.
Query 4
Bob goes from 5 towards 1 and never meets 6.
Query 5
Bob goes from 1 away from 1 and meets finds Oliver at 9.
he can take the following two paths 
1 -> 2 -> 6 -> 9
OR
1 -> 2 -> 7 -> 8
9 appears in atleast one of them

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an integer N denoting the Length of a line segment. You need to cut the line segment in such a way that the cut length of a line segment each time is either x , y or z. Here x, y, and z are integers.
After performing all the cut operations, your total number of cut segments must be maximum.
Note: if no segment can be cut then return 0.
Example 1:
Input:
N = 4
x = 2, y = 1, z = 1
Output: 4
Explanation:Total length is 4, and the cut
lengths are 2, 1 and 1.  We can make
maximum 4 segments each of length 1.
Example 2:
Input:
N = 5
x = 5, y = 3, z = 2
Output: 2
Explanation: Here total length is 5, and
the cut lengths are 5, 3 and 2. We can
make two segments of lengths 3 and 2.
Your Task:
You only need to complete the function maximizeTheCuts() that takes n, x, y, z as parameters and returns max number cuts.
Expected Time Complexity : O(N)
Expected Auxiliary Space: O(N)
Constraints
1 <= N, x, y, z <= 10^{4}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef likes strings a lot but he likes palindromic strings even more. Today he found an old string s in his garage. The string is so old that some of its characters have faded and are unidentifiable now. Faded characters in the string are represented by '.' whereas other characters are lower case Latin alphabets i.e ['a'-'z'].

Chef being the palindrome lover decided to construct the lexicographically smallest palindrome by filling each of the faded character ('.') with a lower case Latin alphabet. Can you please help him completing the task?

-----Input-----
First line of input contains a single integer T denoting the number of test cases. T test cases follow.
First and the only line of each case contains string s denoting the old string that chef has found in his garage.

-----Output-----
For each test case, print lexicographically smallest palindrome after filling each faded character - if it possible to construct one. Print -1 otherwise.

-----Constraints-----
- 1 ≤ T ≤ 50
- 1 ≤ |s| ≤ 12345
- String s consists of ['a'-'z'] and '.' only.

-----Subtasks-----Subtask #1 (47 points)
- 1 ≤ T ≤ 50, 1 ≤ |S| ≤ 123
Subtask #2 (53 points)
- 1 ≤ T ≤ 50, 1 ≤ |S| ≤ 12345

-----Example-----Input
3
a.ba
cb.bc
a.b

Output
abba
cbabc
-1

-----Explanation-----
In example 1, you can create a palindrome by filling the faded character by 'b'.
In example 2, you can replace the faded character by any character from 'a' to 'z'. We fill it by 'a', as it will generate the lexicographically smallest palindrome.
In example 3, it is not possible to make the string s a palindrome.

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
Sometimes one has to spell email addresses over the phone. Then one usually pronounces a dot as dot, an at sign as at. As a result, we get something like vasyaatgmaildotcom. Your task is to transform it into a proper email address ([[email protected]](/cdn-cgi/l/email-protection)). 

It is known that a proper email address contains only such symbols as . @ and lower-case Latin letters, doesn't start with and doesn't end with a dot. Also, a proper email address doesn't start with and doesn't end with an at sign. Moreover, an email address contains exactly one such symbol as @, yet may contain any number (possible, zero) of dots. 

You have to carry out a series of replacements so that the length of the result was as short as possible and it was a proper email address. If the lengths are equal, you should print the lexicographically minimal result. 

Overall, two variants of replacement are possible: dot can be replaced by a dot, at can be replaced by an at.

Input Specification:
The first line contains the email address description. It is guaranteed that that is a proper email address with all the dots replaced by dot an the at signs replaced by at. The line is not empty and its length does not exceed 100 symbols.

Output Specification:
Print the shortest email address, from which the given line could be made by the described above replacements. If there are several solutions to that problem, print the lexicographically minimal one (the lexicographical comparison of the lines are implemented with an operator &lt; in modern programming languages).

In the ASCII table the symbols go in this order: . @ ab...z

Demo Input:
['vasyaatgmaildotcom\n', 'dotdotdotatdotdotat\n', 'aatt\n']

Demo Output:
['[email\xa0protected]\n', '[email\xa0protected]\n', 'a@t\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The Head Chef is receiving a lot of orders for cooking the best of the problems lately. For this, he organized an hiring event to hire some talented Chefs. He gave the following problem to test the skills of the participating Chefs. Can you solve this problem and be eligible for getting hired by Head Chef.

A non-negative number n is said to be magical if it satisfies the following property. Let S denote the multi-set of numbers corresponding to the non-empty subsequences of the digits of the number n in decimal representation. Please note that the numbers in the set S can have leading zeros. Let us take an element s of the multi-set S, prod(s) denotes the product of all the digits of number s in decimal representation. 
The number n will be called magical if sum of prod(s) for all elements s in S, is even. 

For example, consider a number 246, its all possible non-empty subsequence will be S = {2, 4, 6, 24, 46, 26, 246}. Products of digits of these subsequences will be {prod(2) = 2, prod(4) = 4, prod(6) = 6, prod(24) = 8, prod(46) = 24, prod(26) = 12, prod(246) = 48, i.e. {2, 4, 6, 8, 24, 12, 48}. Sum of all of these is 104, which is even. Hence 246 is a magical number.

Please note that multi-set S can contain repeated elements, e.g. if number is 55, then S = {5, 5, 55}. Products of digits of these subsequences will be {prod(5) = 5, prod(5) = 5, prod(55) = 25}, i.e. {5, 5, 25}. Sum of all of these is 35 which is odd. Hence 55 is not a 
magical number.

Consider a number 204, then S = {2, 0, 4, 20, 04, 24, 204}. Products of digits of these subsequences will be {2, 0, 4, 0, 0, 8, 0}. Sum of all these elements will be 14 which is even. So 204 is a magical number.

The task was to simply find the Kth magical number.

-----Input-----
- First line of the input contains an integer T denoting the number of test cases.
- Each of the next T lines contains a single integer K.

-----Output-----
For each test case, print a single integer corresponding to the Kth magical number.

-----Constraints-----
- 1 ≤ T ≤ 105
- 1 ≤ K ≤ 1012.

-----Subtasks-----
Subtask #1 : (20 points)
- 1 ≤ T ≤ 100
- 1 ≤ K ≤ 104.

Subtask 2 : (80 points) Original Constraints

-----Example-----
Input:
2
2
5

Output:
2
8

-----Explanation-----
Example case 1.
2 is the 2nd magical number, since it satisfies the property of the magical number. The first magical number will be of course 0.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a sequence of integers $a_1, a_2, ..., a_N$. An element ak is said to be an average element if there are indices $i, j$ (with $i \neq  j$) such that $a_k = \frac{a_i + a_j}{2}$.
In the sequence
371022171537102217153 \quad 7 \quad 10 \quad 22 \quad 17 \quad 15
for $i=1, j=5$ and $k=3$, we get $a_k = \frac{a_i + a_j}{2}$. Thus $a_3 = 10$ is an average element in this sequence. You can check that $a_3$ is the only average element in this sequence.
Consider the sequence
371031837103183 \quad 7 \quad 10 \quad 3 \quad 18
With $i=1, j=4$ and $k=1$ we get $a_k = \frac{a_i + a_j}{2}$. Thus $a_1=3$ is an average element. We could also choose $i=1, j=4$ and $k=4$ and get $a_k = \frac{a_i + a_j}{2}$. You can check that $a_1$ and $a_4$ are the only average elements of this sequence.
On the other hand, the sequence
38111730381117303 \quad 8 \quad 11 \quad 17 \quad 30
has no average elements.
Your task is to count the number of average elements in the given sequence.

-----Input:-----
The first line contains a single integer $N$ indicating the number of elements in the sequence. This is followed by $N$ lines containing one integer each (Line $i+1$ contains $a_i$). (You may assume that $a_i + a_j$ would not exceed MAXINT for any $i$ and $j$).

-----Output:-----
The output must consist of a single line containing a single integer $k$ indicating the number of average elements in the given sequence.

-----Constraints:-----
- You may assume that $1 \leq N \leq 10000$.
- In $30 \%$ of the inputs $1 \leq N \leq 200$.
- In $60 \%$ of the inputs $1 \leq N \leq 5000$.

-----Sample Input 1:-----
6
3
7
10
17
22
15

-----Sample Output 1:-----
1

-----Sample Input 2:-----
5
3
7
10
3
18

-----Sample Output 2:-----
2

-----Sample Input 3;-----
5
3
8
11
17
30

-----Sample Output 3:-----
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Inbox (100500)

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Over time, Alexey's mail box got littered with too many letters. Some of them are read, while others are unread.

Alexey's mail program can either show a list of all letters or show the content of a single letter. As soon as the program shows the content of an unread letter, it becomes read letter (if the program shows the content of a read letter nothing happens). In one click he can do any of the following operations:
-  Move from the list of letters to the content of any single letter.-  Return to the list of letters from single letter viewing mode.-  In single letter viewing mode, move to the next or to the previous letter in the list. You cannot move from the first letter to the previous one or from the last letter to the next one.
The program cannot delete the letters from the list or rearrange them.

Alexey wants to read all the unread letters and go watch football. Now he is viewing the list of all letters and for each letter he can see if it is read or unread. What minimum number of operations does Alexey need to perform to read all unread letters?

Input Specification:
The first line contains a single integer *n* (1<=≤<=*n*<=≤<=1000) — the number of letters in the mailbox.

The second line contains *n* space-separated integers (zeros and ones) — the state of the letter list. The *i*-th number equals either 1, if the *i*-th number is unread, or 0, if the *i*-th letter is read.

Output Specification:
Print a single number — the minimum number of operations needed to make all the letters read.

Demo Input:
['5\n0 1 0 1 0\n', '5\n1 1 0 0 1\n', '2\n0 0\n']

Demo Output:
['3\n', '4\n', '0\n']

Note:
In the first sample Alexey needs three operations to cope with the task: open the second letter, move to the third one, move to the fourth one.

In the second sample the action plan: open the first letter, move to the second letter, return to the list, open the fifth letter.

In the third sample all letters are already read.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Being tired of participating in too many Codeforces rounds, Gildong decided to take some rest in a park. He sat down on a bench, and soon he found two rabbits hopping around. One of the rabbits was taller than the other.

He noticed that the two rabbits were hopping towards each other. The positions of the two rabbits can be represented as integer coordinates on a horizontal line. The taller rabbit is currently on position $x$, and the shorter rabbit is currently on position $y$ ($x \lt y$). Every second, each rabbit hops to another position. The taller rabbit hops to the positive direction by $a$, and the shorter rabbit hops to the negative direction by $b$.

 [Image] 

For example, let's say $x=0$, $y=10$, $a=2$, and $b=3$. At the $1$-st second, each rabbit will be at position $2$ and $7$. At the $2$-nd second, both rabbits will be at position $4$.

Gildong is now wondering: Will the two rabbits be at the same position at the same moment? If so, how long will it take? Let's find a moment in time (in seconds) after which the rabbits will be at the same point.


-----Input-----

Each test contains one or more test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$).

Each test case contains exactly one line. The line consists of four integers $x$, $y$, $a$, $b$ ($0 \le x \lt y \le 10^9$, $1 \le a,b \le 10^9$) — the current position of the taller rabbit, the current position of the shorter rabbit, the hopping distance of the taller rabbit, and the hopping distance of the shorter rabbit, respectively.


-----Output-----

For each test case, print the single integer: number of seconds the two rabbits will take to be at the same position.

If the two rabbits will never be at the same position simultaneously, print $-1$.


-----Example-----
Input
5
0 10 2 3
0 10 3 3
900000000 1000000000 1 9999999
1 2 1 1
1 3 1 1

Output
2
-1
10
-1
1



-----Note-----

The first case is explained in the description.

In the second case, each rabbit will be at position $3$ and $7$ respectively at the $1$-st second. But in the $2$-nd second they will be at $6$ and $4$ respectively, and we can see that they will never be at the same position since the distance between the two rabbits will only increase afterward.

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