apaz/codeforces-genesys huggingface dataset:
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Jon fought bravely to rescue the wildlings who were attacked by the white-walkers at Hardhome. On his arrival, Sam tells him that he wants to go to Oldtown to train at the Citadel to become a maester, so he can return and take the deceased Aemon's place as maester of Castle Black. Jon agrees to Sam's proposal and Sam sets off his journey to the Citadel. However becoming a trainee at the Citadel is not a cakewalk and hence the maesters at the Citadel gave Sam a problem to test his eligibility.

Initially Sam has a list with a single element n. Then he has to perform certain operations on this list. In each operation Sam must remove any element x, such that x > 1, from the list and insert at the same position $$\left\lfloor \frac{x}{2} \right\rfloor$$, $$x \mod 2$$, $$\left\lfloor \frac{x}{2} \right\rfloor$$ sequentially. He must continue with these operations until all the elements in the list are either 0 or 1.

Now the masters want the total number of 1s in the range l to r (1-indexed). Sam wants to become a maester but unfortunately he cannot solve this problem. Can you help Sam to pass the eligibility test?

## Input Format
The first line contains three integers n, l, r (0 ≤ n < 250, 0 ≤ r - l ≤ 105, r ≥ 1, l ≥ 1) – initial element and the range l to r.

It is guaranteed that r is not greater than the length of the final list.

## Output Format
Output the total number of 1s in the range l to r in the final sequence.

## Examples
```input
7 2 5
```
```output
4
```
-----
```input
10 3 10
```
```output
5
```

## Note
Consider first example:

$$[7] \rightarrow [3,1,3] \rightarrow [1,1,1,1,3] \rightarrow [1,1,1,1,1,1] \rightarrow [1,1,1,1,1,1]$$

Elements on positions from 2-nd to 5-th in list is [1, 1, 1, 1]. The number of ones is 4.

For the second example:

$$[10] \rightarrow [1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1]$$

Elements on positions from 3-rd to 10-th in list is [1, 1, 1, 0, 1, 0, 1, 0]. The number of ones is 5.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 4.0 seconds
Memory limit: 256.0 MB

# Problem
Jon Snow now has to fight with White Walkers. He has n rangers, each of which has his own strength. Also Jon Snow has his favourite number x. Each ranger can fight with a white walker only if the strength of the white walker equals his strength. He however thinks that his rangers are weak and need to improve. Jon now thinks that if he takes the bitwise XOR of strengths of some of rangers with his favourite number x, he might get soldiers of high strength. So, he decided to do the following operation k times:

1. Arrange all the rangers in a straight line in the order of increasing strengths.
2. Take the bitwise XOR (is written as $$\bigcirc$$) of the strength of each alternate ranger with x and update it's strength.

1. The strength of first ranger is updated to $$5 \oplus 2$$, i.e. 7.
2. The strength of second ranger remains the same, i.e. 7.
3. The strength of third ranger is updated to $$9 \oplus 2$$, i.e. 11.
4. The strength of fourth ranger remains the same, i.e. 11.
5. The strength of fifth ranger is updated to $$15 \oplus 2$$, i.e. 13.

Now, Jon wants to know the maximum and minimum strength of the rangers after performing the above operations k times. He wants your help for this task. Can you help him?

## Input Format
First line consists of three integers n, k, x (1 ≤ n ≤ 105, 0 ≤ k ≤ 105, 0 ≤ x ≤ 103) — number of rangers Jon has, the number of times Jon will carry out the operation and Jon's favourite number respectively.

Second line consists of n integers representing the strengths of the rangers a1, a2, ..., an (0 ≤ ai ≤ 103).

## Output Format
Output two integers, the maximum and the minimum strength of the rangers after performing the operation k times.

## Examples
```input
5 1 2
9 7 11 15 5
```
```output
13 7
```
-----
```input
2 100000 569
605 986
```
```output
986 605
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Jon Snow is on the lookout for some orbs required to defeat the white walkers. There are k different types of orbs and he needs at least one of each. One orb spawns daily at the base of a Weirwood tree north of the wall. The probability of this orb being of any kind is equal. As the north of wall is full of dangers, he wants to know the minimum number of days he should wait before sending a ranger to collect the orbs such that the probability of him getting at least one of each kind of orb is at least $${ \frac { p _ { i } - \epsilon } { 2 0 0 0 } }$$, where ε < 10 - 7.

To better prepare himself, he wants to know the answer for q different values of pi. Since he is busy designing the battle strategy with Sam, he asks you for your help.

## Input Format
First line consists of two space separated integers k, q (1 ≤ k, q ≤ 1000) — number of different kinds of orbs and number of queries respectively.

Each of the next q lines contain a single integer pi (1 ≤ pi ≤ 1000) — i-th query.

## Output Format
Output q lines. On i-th of them output single integer — answer for i-th query.

## Examples
```input
1 1
1
```
```output
1
```
-----
```input
2 2
1
2
```
```output
2
2
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 256.0 MB

# Problem
Sam has been teaching Jon the Game of Stones to sharpen his mind and help him devise a strategy to fight the white walkers. The rules of this game are quite simple:

- The game starts with n piles of stones indexed from 1 to n. The i-th pile contains si stones.
- The players make their moves alternatively. A move is considered as removal of some number of stones from a pile. Removal of 0 stones does not count as a move.
- The player who is unable to make a move loses.

Now Jon believes that he is ready for battle, but Sam does not think so. To prove his argument, Sam suggested that they play a modified version of the game.

In this modified version, no move can be made more than once on a pile. For example, if 4 stones are removed from a pile, 4 stones cannot be removed from that pile again.

Sam sets up the game and makes the first move. Jon believes that Sam is just trying to prevent him from going to battle. Jon wants to know if he can win if both play optimally.

## Input Format
First line consists of a single integer n (1 ≤ n ≤ 106) — the number of piles.

Each of next n lines contains an integer si (1 ≤ si ≤ 60) — the number of stones in i-th pile.

## Output Format
Print a single line containing "YES" (without quotes) if Jon wins, otherwise print "NO" (without quotes)

## Examples
```input
1
5
```
```output
NO
```
-----
```input
2
1
2
```
```output
YES
```

## Note
In the first case, Sam removes all the stones and Jon loses.

In second case, the following moves are possible by Sam: $$\{1,2\} \rightarrow \{0,2\}, \{1,2\} \rightarrow \{1,0\}, \{1,2\} \rightarrow \{1,1\}$$

In each of these cases, last move can be made by Jon to win the game as follows: $${ \{ 0, 2 \} } \rightarrow { \{ 0, 0 \} }, { \{ 1, 0 \} } \rightarrow { \{ 0, 0 \} }, { \{ 1, 1 \} } \rightarrow { \{ 0, 1 \} }$$

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Tarly has two different type of items, food boxes and wine barrels. There are f food boxes and w wine barrels. Tarly stores them in various stacks and each stack can consist of either food boxes or wine barrels but not both. The stacks are placed in a line such that no two stacks of food boxes are together and no two stacks of wine barrels are together.

The height of a stack is defined as the number of items in the stack. Two stacks are considered different if either their heights are different or one of them contains food and other contains wine.

Jon Snow doesn't like an arrangement if any stack of wine barrels has height less than or equal to h. What is the probability that Jon Snow will like the arrangement if all arrangement are equiprobably?

Two arrangement of stacks are considered different if exists such i, that i-th stack of one arrangement is different from the i-th stack of the other arrangement.

## Input Format
The first line of input contains three integers f, w, h (0 ≤ f, w, h ≤ 105) — number of food boxes, number of wine barrels and h is as described above. It is guaranteed that he has at least one food box or at least one wine barrel.

## Output Format
Output the probability that Jon Snow will like the arrangement. The probability is of the form $$\frac{p}{q}$$, then you need to output a single integer p·q - 1 mod (109 + 7).

## Examples
```input
1 1 1
```
```output
0
```
-----
```input
1 2 1
```
```output
666666672
```

## Note
In the first example f  =  1, w = 1 and h = 1, there are only two possible arrangement of stacks and Jon Snow doesn't like any of them.

In the second example f = 1, w = 2 and h = 1, there are three arrangements. Jon Snow likes the (1) and (3) arrangement. So the probabilty is $$\frac{2}{3}$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 512.0 MB

# Problem
Given a rooted tree with n nodes. The Night King removes exactly one node from the tree and all the edges associated with it. Doing this splits the tree and forms a forest. The node which is removed is not a part of the forest.

The root of a tree in the forest is the node in that tree which does not have a parent. We define the strength of the forest as the size of largest tree in forest.

Jon Snow wants to minimize the strength of the forest. To do this he can perform the following operation at most once.

He removes the edge between a node and its parent and inserts a new edge between this node and any other node in forest such that the total number of trees in forest remain same.

For each node v you need to find the minimum value of strength of the forest formed when node v is removed.

## Input Format
The first line of the input contains an integer n (1  ≤  n  ≤  105) — the number of vertices in the tree. Each of the next n lines contains a pair of vertex indices ui and vi (1  ≤  ui,  vi  ≤  n) where ui is the parent of vi. If ui = 0 then vi is the root.

## Output Format
Print n line each containing a single integer. The i-th of them should be equal to minimum value of strength of forest formed when i-th node is removed and Jon Snow performs the operation described above at most once.

## Examples
```input
10
0 1
1 2
1 3
1 4
2 5
2 6
3 7
4 8
4 9
5 10
```
```output
3
4
5
5
5
9
9
9
9
9
```
-----
```input
2
2 1
0 2
```
```output
1
1
```

## Note
The tree for first test case is depicted below.  When you remove the first node, the tree splits to form the following forest. The strength of this forest is 4.  Jon Snow now changes the parent of vertex 10 from 5 to 3. The strength of forest now becomes 3.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Masha really loves algebra. On the last lesson, her strict teacher Dvastan gave she new exercise.

You are given geometric progression b defined by two integers b1 and q. Remind that a geometric progression is a sequence of integers b1, b2, b3, ..., where for each i > 1 the respective term satisfies the condition bi = bi - 1·q, where q is called the common ratio of the progression. Progressions in Uzhlyandia are unusual: both b1 and q can equal 0. Also, Dvastan gave Masha m "bad" integers a1, a2, ..., am, and an integer l.

Masha writes all progression terms one by one onto the board (including repetitive) while condition |bi| ≤ l is satisfied (|x| means absolute value of x). There is an exception: if a term equals one of the "bad" integers, Masha skips it (doesn't write onto the board) and moves forward to the next term.

But the lesson is going to end soon, so Masha has to calculate how many integers will be written on the board. In order not to get into depression, Masha asked you for help: help her calculate how many numbers she will write, or print "inf" in case she needs to write infinitely many integers.

## Input Format
The first line of input contains four integers b1, q, l, m (-109 ≤ b1, q ≤ 109, 1 ≤ l ≤ 109, 1 ≤ m ≤ 105) — the initial term and the common ratio of progression, absolute value of maximal number that can be written on the board and the number of "bad" integers, respectively.

The second line contains m distinct integers a1, a2, ..., am (-109 ≤ ai ≤ 109) — numbers that will never be written on the board.

## Output Format
Print the only integer, meaning the number of progression terms that will be written on the board if it is finite, or "inf" (without quotes) otherwise.

## Examples
```input
3 2 30 4
6 14 25 48
```
```output
3
```
-----
```input
123 1 2143435 4
123 11 -5453 141245
```
```output
0
```
-----
```input
123 1 2143435 4
54343 -13 6 124
```
```output
inf
```

## Note
In the first sample case, Masha will write integers 3, 12, 24. Progression term 6 will be skipped because it is a "bad" integer. Terms bigger than 24 won't be written because they exceed l by absolute value.

In the second case, Masha won't write any number because all terms are equal 123 and this is a "bad" integer.

In the third case, Masha will write infinitely integers 123.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Sagheer is walking in the street when he comes to an intersection of two roads. Each road can be represented as two parts where each part has 3 lanes getting into the intersection (one for each direction) and 3 lanes getting out of the intersection, so we have 4 parts in total. Each part has 4 lights, one for each lane getting into the intersection (l — left, s — straight, r — right) and a light p for a pedestrian crossing.

An accident is possible if a car can hit a pedestrian. This can happen if the light of a pedestrian crossing of some part and the light of a lane that can get to or from that same part are green at the same time.

Now, Sagheer is monitoring the configuration of the traffic lights. Your task is to help him detect whether an accident is possible.

## Input Format
The input consists of four lines with each line describing a road part given in a counter-clockwise order.

Each line contains four integers l, s, r, p — for the left, straight, right and pedestrian lights, respectively. The possible values are 0 for red light and 1 for green light.

## Output Format
On a single line, print "YES" if an accident is possible, and "NO" otherwise.

## Examples
```input
1 0 0 1
0 1 0 0
0 0 1 0
0 0 0 1
```
```output
YES
```
-----
```input
0 1 1 0
1 0 1 0
1 1 0 0
0 0 0 1
```
```output
NO
```
-----
```input
1 0 0 0
0 0 0 1
0 0 0 0
1 0 1 0
```
```output
NO
```

## Note
In the first example, some accidents are possible because cars of part 1 can hit pedestrians of parts 1 and 4. Also, cars of parts 2 and 3 can hit pedestrians of part 4.

In the second example, no car can pass the pedestrian crossing of part 4 which is the only green pedestrian light. So, no accident can occur.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
On his trip to Luxor and Aswan, Sagheer went to a Nubian market to buy some souvenirs for his friends and relatives. The market has some strange rules. It contains n different items numbered from 1 to n. The i-th item has base cost ai Egyptian pounds. If Sagheer buys k items with indices x1, x2, ..., xk, then the cost of item xj is axj + xj·k for 1 ≤ j ≤ k. In other words, the cost of an item is equal to its base cost in addition to its index multiplied by the factor k.

Sagheer wants to buy as many souvenirs as possible without paying more than S Egyptian pounds. Note that he cannot buy a souvenir more than once. If there are many ways to maximize the number of souvenirs, he will choose the way that will minimize the total cost. Can you help him with this task?

## Input Format
The first line contains two integers n and S (1 ≤ n ≤ 105 and 1 ≤ S ≤ 109) — the number of souvenirs in the market and Sagheer's budget.

The second line contains n space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 105) — the base costs of the souvenirs.

## Output Format
On a single line, print two integers k, T — the maximum number of souvenirs Sagheer can buy and the minimum total cost to buy these k souvenirs.

## Examples
```input
3 11
2 3 5
```
```output
2 11
```
-----
```input
4 100
1 2 5 6
```
```output
4 54
```
-----
```input
1 7
7
```
```output
0 0
```

## Note
In the first example, he cannot take the three items because they will cost him [5, 9, 14] with total cost 28. If he decides to take only two items, then the costs will be [4, 7, 11]. So he can afford the first and second items.

In the second example, he can buy all items as they will cost him [5, 10, 17, 22].

In the third example, there is only one souvenir in the market which will cost him 8 pounds, so he cannot buy it.

Now solve the problem and return the code.