vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
In research, it is tough to determine how good of a researcher you are. One way that people determine how good you are is by looking at your $H$-Index.

Each paper has a certain number of citations. Your $H$-Index is the largest number $H$ such that you have $H$ papers with at least $H$ citations. Given the number of citations on each paper you have written, what is your $H$-Index?

-----Input-----
The first line of input contains a single integer $n$ ($1 \leq n \leq 100000$), which is the number of papers you have written.

The next $n$ lines describe the papers. Each of these lines contains a single integer $c$ ($0 \leq c \leq 1000000000$), which is the number of citations that this paper has.

-----Output-----
Display your $H$-Index.

-----Examples-----
Sample Input 1:
5
7
1
2
1
5
Sample Output 1:
2

Sample Input 2:
5
7
1
3
1
5
Sample Output 2:
3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Unicode Transformation Format – 8-bit
As the name suggests UTF-8 was designed to encode data in a stream of bytes.

It works by splitting the bits up in multiples of eight. This is achieved by inserting headers to mark in how many bytes the bits were split. If the bits need to be split in two, the header `110` is added as prefix leaving five bits of the byte for the rest of the data. Followed by a continuation byte.

A continuation byte always start with `10` leaving six bits for data.
For a three-way split: the header `1110` is added with two continuation bytes and for four: `11110` with three continuation bytes. The number of ones at the start of the first byte denotes the number of bytes the data was split in.
# Task
Your task is to write two functions:
1. `to_utf8_binary`: which encodes a string to a bitstring using UTF-8 encoding.
2. `from_utf8_binary`: which does the reverse.

- Layout of UTF-8 byte sequences:
```
# BYTES  FIRST CODE POINT  LAST CODE POINT    BYTE 1      BYTE 2      BYTE 3      BYTE 4
    1                   0              127    0xxxxxxx  
    2                 128             2047    110xxxxx    10xxxxxx
    3                2048            65535    1110xxxx    10xxxxxx    10xxxxxx  
    4               65536          1114111    11110xxx    10xxxxxx    10xxxxxx    10xxxxxx
```

# Examples
```
ENCODE
 A  -> 1000001         -> 01000001
 八 -> 101000101101011 -> 1110-0101 10-000101 10-101011
 
DECODE
 110-00010 10-100111                     -> 10100111          -> §
 11110-000 10-010000 10-001010 10-001100 -> 10000001010001100 -> 𐊌
```
* Spaces and hyphens just for clarity
- https://en.wikipedia.org/wiki/UTF-8#Encoding

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Strings of yarn have been popular in Catland for ages. Which cat has not spent many a lazy afternoon bouncing around a ball of yarn? Lately however, strings of yarn have gotten competition: strings of characters. It turns out that these are almost as much fun as yarn, and generally much safer as well (so far, no cat has had to call 911 on account of any character string-related entanglement accidents). 

Naturally, some strings are more stylish than others, and for cool cats it is important to engage in their string-playing pastime with style. The meow factor of a string $S$ is the minimum number of operations needed to transform $S$ into a string $S’$ which contains the word “meow” as a substring, where an operation is one of the following four:
 - Insert an arbitrary character anywhere into the string.
 - Delete an arbitrary character anywhere from the string.
 - Replace any character in the string by an arbitrary character.
 - Swap any two adjacent characters in the string.

Write a program to compute the meow factor of a string of characters.

-----Input-----
The input consists of a single line containing a string $S$, consisting only of lower-case letters ‘a’-‘z’. The length of $S$ is at least $1$ and at most $10^6$.

-----Output-----
Output the meow factor of $S$.

-----Examples-----
Sample Input:
pastimeofwhimsy
Sample Output:
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a sequence $s$ consisting of $n$ digits from $1$ to $9$.

You have to divide it into at least two segments (segment — is a consecutive sequence of elements) (in other words, you have to place separators between some digits of the sequence) in such a way that each element belongs to exactly one segment and if the resulting division will be represented as an integer numbers sequence then each next element of this sequence will be strictly greater than the previous one.

More formally: if the resulting division of the sequence is $t_1, t_2, \dots, t_k$, where $k$ is the number of element in a division, then for each $i$ from $1$ to $k-1$ the condition $t_{i} < t_{i + 1}$ (using numerical comparing, it means that the integer representations of strings are compared) should be satisfied.

For example, if $s=654$ then you can divide it into parts $[6, 54]$ and it will be suitable division. But if you will divide it into parts $[65, 4]$ then it will be bad division because $65 > 4$. If $s=123$ then you can divide it into parts $[1, 23]$, $[1, 2, 3]$ but not into parts $[12, 3]$.

Your task is to find any suitable division for each of the $q$ independent queries.


-----Input-----

The first line of the input contains one integer $q$ ($1 \le q \le 300$) — the number of queries.

The first line of the $i$-th query contains one integer number $n_i$ ($2 \le n_i \le 300$) — the number of digits in the $i$-th query.

The second line of the $i$-th query contains one string $s_i$ of length $n_i$ consisting only of digits from $1$ to $9$.


-----Output-----

If the sequence of digits in the $i$-th query cannot be divided into at least two parts in a way described in the problem statement, print the single line "NO" for this query.

Otherwise in the first line of the answer to this query print "YES", on the second line print $k_i$ — the number of parts in your division of the $i$-th query sequence and in the third line print $k_i$ strings $t_{i, 1}, t_{i, 2}, \dots, t_{i, k_i}$ — your division. Parts should be printed in order of the initial string digits. It means that if you write the parts one after another without changing their order then you'll get the string $s_i$.

See examples for better understanding.


-----Example-----
Input
4
6
654321
4
1337
2
33
4
2122

Output
YES
3
6 54 321
YES
3
1 3 37
NO
YES
2
21 22

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two matrices $A$ and $B$. Each matrix contains exactly $n$ rows and $m$ columns. Each element of $A$ is either $0$ or $1$; each element of $B$ is initially $0$.

You may perform some operations with matrix $B$. During each operation, you choose any submatrix of $B$ having size $2 \times 2$, and replace every element in the chosen submatrix with $1$. In other words, you choose two integers $x$ and $y$ such that $1 \le x < n$ and $1 \le y < m$, and then set $B_{x, y}$, $B_{x, y + 1}$, $B_{x + 1, y}$ and $B_{x + 1, y + 1}$ to $1$.

Your goal is to make matrix $B$ equal to matrix $A$. Two matrices $A$ and $B$ are equal if and only if every element of matrix $A$ is equal to the corresponding element of matrix $B$.

Is it possible to make these matrices equal? If it is, you have to come up with a sequence of operations that makes $B$ equal to $A$. Note that you don't have to minimize the number of operations.


-----Input-----

The first line contains two integers $n$ and $m$ ($2 \le n, m \le 50$).

Then $n$ lines follow, each containing $m$ integers. The $j$-th integer in the $i$-th line is $A_{i, j}$. Each integer is either $0$ or $1$.


-----Output-----

If it is impossible to make $B$ equal to $A$, print one integer $-1$.

Otherwise, print any sequence of operations that transforms $B$ into $A$ in the following format: the first line should contain one integer $k$ — the number of operations, and then $k$ lines should follow, each line containing two integers $x$ and $y$ for the corresponding operation (set $B_{x, y}$, $B_{x, y + 1}$, $B_{x + 1, y}$ and $B_{x + 1, y + 1}$ to $1$). The condition $0 \le k \le 2500$ should hold.


-----Examples-----
Input
3 3
1 1 1
1 1 1
0 1 1

Output
3
1 1
1 2
2 2

Input
3 3
1 0 1
1 0 1
0 0 0

Output
-1

Input
3 2
0 0
0 0
0 0

Output
0



-----Note-----

The sequence of operations in the first example: $\begin{matrix} 0 & 0 & 0 & & 1 & 1 & 0 & & 1 & 1 & 1 & & 1 & 1 & 1 \\ 0 & 0 & 0 & \rightarrow & 1 & 1 & 0 & \rightarrow & 1 & 1 & 1 & \rightarrow & 1 & 1 & 1 \\ 0 & 0 & 0 & & 0 & 0 & 0 & & 0 & 0 & 0 & & 0 & 1 & 1 \end{matrix}$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Okabe and Banana Trees

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Okabe needs bananas for one of his experiments for some strange reason. So he decides to go to the forest and cut banana trees.

Consider the point (*x*,<=*y*) in the 2D plane such that *x* and *y* are integers and 0<=≤<=*x*,<=*y*. There is a tree in such a point, and it has *x*<=+<=*y* bananas. There are no trees nor bananas in other points. Now, Okabe draws a line with equation . Okabe can select a single rectangle with axis aligned sides with all points on or under the line and cut all the trees in all points that are inside or on the border of this rectangle and take their bananas. Okabe's rectangle can be degenerate; that is, it can be a line segment or even a point.

Help Okabe and find the maximum number of bananas he can get if he chooses the rectangle wisely.

Okabe is sure that the answer does not exceed 1018. You can trust him.

Input Specification:
The first line of input contains two space-separated integers *m* and *b* (1<=≤<=*m*<=≤<=1000, 1<=≤<=*b*<=≤<=10000).

Output Specification:
Print the maximum number of bananas Okabe can get from the trees he cuts.

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

Demo Output:
['30\n', '25\n']

Note:
The graph above corresponds to sample test 1. The optimal rectangle is shown in red and has 30 bananas.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a range of positive integers from $l$ to $r$.

Find such a pair of integers $(x, y)$ that $l \le x, y \le r$, $x \ne y$ and $x$ divides $y$.

If there are multiple answers, print any of them.

You are also asked to answer $T$ independent queries.


-----Input-----

The first line contains a single integer $T$ ($1 \le T \le 1000$) — the number of queries.

Each of the next $T$ lines contains two integers $l$ and $r$ ($1 \le l \le r \le 998244353$) — inclusive borders of the range.

It is guaranteed that testset only includes queries, which have at least one suitable pair.


-----Output-----

Print $T$ lines, each line should contain the answer — two integers $x$ and $y$ such that $l \le x, y \le r$, $x \ne y$ and $x$ divides $y$. The answer in the $i$-th line should correspond to the $i$-th query from the input.

If there are multiple answers, print any of them.


-----Example-----
Input
3
1 10
3 14
1 10

Output
1 7
3 9
5 10

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Snuke has a fair N-sided die that shows the integers from 1 to N with equal probability and a fair coin. He will play the following game with them:

1. Throw the die. The current score is the result of the die.
2. As long as the score is between 1 and K-1 (inclusive), keep flipping the coin. The score is doubled each time the coin lands heads up, and the score becomes 0 if the coin lands tails up.
3. The game ends when the score becomes 0 or becomes K or above. Snuke wins if the score is K or above, and loses if the score is 0.



You are given N and K. Find the probability that Snuke wins the game.

Constraints

* 1 ≤ N ≤ 10^5
* 1 ≤ K ≤ 10^5
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N K


Output

Print the probability that Snuke wins the game. The output is considered correct when the absolute or relative error is at most 10^{-9}.

Examples

Input

3 10


Output

0.145833333333


Input

100000 5


Output

0.999973749998

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Xenia the vigorous detective faced *n* (*n*<=≥<=2) foreign spies lined up in a row. We'll consider the spies numbered from 1 to *n* from left to right. 

Spy *s* has an important note. He has to pass the note to spy *f*. Xenia interrogates the spies in several steps. During one step the spy keeping the important note can pass the note to one of his neighbours in the row. In other words, if this spy's number is *x*, he can pass the note to another spy, either *x*<=-<=1 or *x*<=+<=1 (if *x*<==<=1 or *x*<==<=*n*, then the spy has only one neighbour). Also during a step the spy can keep a note and not pass it to anyone.

But nothing is that easy. During *m* steps Xenia watches some spies attentively. Specifically, during step *t**i* (steps are numbered from 1) Xenia watches spies numbers *l**i*,<=*l**i*<=+<=1,<=*l**i*<=+<=2,<=...,<=*r**i* (1<=≤<=*l**i*<=≤<=*r**i*<=≤<=*n*). Of course, if during some step a spy is watched, he can't do anything: neither give the note nor take it from some other spy. Otherwise, Xenia reveals the spies' cunning plot. Nevertheless, if the spy at the current step keeps the note, Xenia sees nothing suspicious even if she watches him.

You've got *s* and *f*. Also, you have the steps during which Xenia watches spies and which spies she is going to watch during each step. Find the best way the spies should act in order to pass the note from spy *s* to spy *f* as quickly as possible (in the minimum number of steps).

Input Specification:
The first line contains four integers *n*, *m*, *s* and *f* (1<=≤<=*n*,<=*m*<=≤<=105; 1<=≤<=*s*,<=*f*<=≤<=*n*; *s*<=≠<=*f*; *n*<=≥<=2). Each of the following *m* lines contains three integers *t**i*,<=*l**i*,<=*r**i* (1<=≤<=*t**i*<=≤<=109,<=1<=≤<=*l**i*<=≤<=*r**i*<=≤<=*n*). It is guaranteed that *t*1<=&lt;<=*t*2<=&lt;<=*t*3<=&lt;<=...<=&lt;<=*t**m*.

Output Specification:
Print *k* characters in a line: the *i*-th character in the line must represent the spies' actions on step *i*. If on step *i* the spy with the note must pass the note to the spy with a lesser number, the *i*-th character should equal "L". If on step *i* the spy with the note must pass it to the spy with a larger number, the *i*-th character must equal "R". If the spy must keep the note at the *i*-th step, the *i*-th character must equal "X".

As a result of applying the printed sequence of actions spy *s* must pass the note to spy *f*. The number of printed characters *k* must be as small as possible. Xenia must not catch the spies passing the note.

If there are miltiple optimal solutions, you can print any of them. It is guaranteed that the answer exists.

Demo Input:
['3 5 1 3\n1 1 2\n2 2 3\n3 3 3\n4 1 1\n10 1 3\n']

Demo Output:
['XXRR\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Each pizza consists of 4 slices. There are N friends and each friend needs exactly X slices. 

Find the minimum number of pizzas they should order to satisfy their appetite.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of two integers N and X, the number of friends and the number of slices each friend wants respectively.

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

For each test case, output the minimum number of pizzas required.

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

$1 ≤ T ≤ 100$
$1 ≤ N, X ≤ 10$

----- Sample Input 1 ------ 
4
1 5
2 6
4 3
3 5

----- Sample Output 1 ------ 
2
3
3
4

----- explanation 1 ------ 
Test case $1$: There is only $1$ friend who requires $5$ slices. If he orders $1$ pizza, he will get only $4$ slices. Thus, at least $2$ pizzas should be ordered to have required number of slices.

Test case $2$: There are $2$ friends who require $6$ slices each. Thus, total $12$ slices are required. To get $12$ slices, they should order $3$ pizzas.

Test case $3$: There are $4$ friends who require $3$ slices each. Thus, total $12$ slices are required. To get $12$ slices, they should order $3$ pizzas.

Test case $4$: There are $3$ friends who require $5$ slices each. Thus, total $15$ slices are required. To get $15$ slices, they should order at least $4$ pizzas.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You have two positive integers *w* and *h*. Your task is to count the number of rhombi which have the following properties: 
 -  Have positive area. -  With vertices at integer points. -  All vertices of the rhombi are located inside or on the border of the rectangle with vertices at points (0,<=0), (*w*,<=0), (*w*,<=*h*), (0,<=*h*). In other words, for all vertices (*x**i*,<=*y**i*) of the rhombus the following conditions should fulfill: 0<=≤<=*x**i*<=≤<=*w* and 0<=≤<=*y**i*<=≤<=*h*. -  Its diagonals are parallel to the axis. 
Count the number of such rhombi.

Let us remind you that a rhombus is a quadrilateral whose four sides all have the same length.

Input Specification:
The first line contains two integers *w* and *h* (1<=≤<=*w*,<=*h*<=≤<=4000) — the rectangle's sizes.

Output Specification:
Print a single number — the number of sought rhombi.

Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specifier.

Demo Input:
['2 2\n', '1 2\n']

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

Note:
In the first example there exists only one such rhombus. Its vertices are located at points (1, 0), (2, 1), (1, 2), (0, 1).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two arrays $a_1, a_2, \dots , a_n$ and $b_1, b_2, \dots , b_m$. Array $b$ is sorted in ascending order ($b_i < b_{i + 1}$ for each $i$ from $1$ to $m - 1$).

You have to divide the array $a$ into $m$ consecutive subarrays so that, for each $i$ from $1$ to $m$, the minimum on the $i$-th subarray is equal to $b_i$. Note that each element belongs to exactly one subarray, and they are formed in such a way: the first several elements of $a$ compose the first subarray, the next several elements of $a$ compose the second subarray, and so on.

For example, if $a = [12, 10, 20, 20, 25, 30]$ and $b = [10, 20, 30]$ then there are two good partitions of array $a$:   $[12, 10, 20], [20, 25], [30]$;  $[12, 10], [20, 20, 25], [30]$. 

You have to calculate the number of ways to divide the array $a$. Since the number can be pretty large print it modulo 998244353.


-----Input-----

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 2 \cdot 10^5$) — the length of arrays $a$ and $b$ respectively.

The second line contains $n$ integers $a_1, a_2, \dots , a_n$ ($1 \le a_i \le 10^9$) — the array $a$.

The third line contains $m$ integers $b_1, b_2, \dots , b_m$ ($1 \le b_i \le 10^9; b_i < b_{i+1}$) — the array $b$.


-----Output-----

In only line print one integer — the number of ways to divide the array $a$ modulo 998244353.


-----Examples-----
Input
6 3
12 10 20 20 25 30
10 20 30

Output
2

Input
4 2
1 3 3 7
3 7

Output
0

Input
8 2
1 2 2 2 2 2 2 2
1 2

Output
7

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The development of algae in a pond is as follows.
Let the total weight of the algae at the beginning of the year i be x_i gram. For i≥2000, the following formula holds:
 - x_{i+1} = rx_i - D
You are given r, D and x_{2000}. Calculate x_{2001}, ..., x_{2010} and print them in order.

-----Constraints-----
 - 2 ≤ r ≤ 5
 - 1 ≤ D ≤ 100
 - D < x_{2000} ≤ 200
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
r D x_{2000}

-----Output-----
Print 10 lines. The i-th line (1 ≤ i ≤ 10) should contain x_{2000+i} as an integer.

-----Sample Input-----
2 10 20

-----Sample Output-----
30
50
90
170
330
650
1290
2570
5130
10250

For example, x_{2001} = rx_{2000} - D = 2 \times 20 - 10 = 30 and x_{2002} = rx_{2001} - D = 2 \times 30 - 10 = 50.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
An LCD panel is composed of a grid of pixels, spaced $1$ alu (“arbitrary length unit”) apart both horizontally and vertically. Wires run along each row and each column, intersecting at the pixels. Wires are numbered beginning with $1$ and proceeding up to a panel-dependent maximum. The vertical wire numbered $1$ lies along the left edge of the panel, and the horizontal wire numbered $1$ lies along the bottom edge of the panel.

A pixel will activate, turning dark, when a current is present along both the vertical and horizontal wire passing through that pixel.

For a period of time, we will send pulses of current down selected wires. The current flows down the wires at a speed of one alu per atu (“arbitrary time unit”). The pulses themselves have a length measured in atus. A pixel activates when current is passing through both intersecting wires at the same time. If the leading edge of a pulse on one wire reaches the intersection at the exact same time that the trailing edge of a pulse on the other wire leaves that intersection, the pixel is not activated.

All pulses in vertical wires start from the bottom of the grid. All pulses in horizontal wires start from the left of the grid. At most one pulse will travel along any one wire.

Given the schedule of pulses to be sent through the wires, determine how many pixels will have been activated by the time all pulses have exited the top and right of the grid.

-----Input-----
The first line contains $n$, the number of current pulses, with $1\le n\le 200000$.

Following this are $n$ lines, each describing a single pulse. Each such line contains four elements, separated from one another by a single space:
 - A single character that is either ‘h’ or ‘v’, indicating the horizontal/vertical direction of the pulse.
 - An integer $t$, $1\le t\le 200000$, denoting the starting time of the pulse. The starting time is considered to be the moment when the leading edge of a vertical [horizontal] pulse crosses horizontal [vertical] wire #$1$.
 - An integer $m$, $1\le m\le 200000$, denoting the length of the pulse.
 - An integer $a$, $1\le a\le 100000$, denoting the wire number (horizontal or vertical) along which the pulse travels.

-----Output-----
Print on a single line the number of pixels that will have activated by the time the last pulse of current has left the grid.

-----Examples-----
Sample Input 1:
4
h 1 4 1
v 2 4 2
h 10 2 2
v 11 2 3
Sample Output 1:
2

Sample Input 2:
4
h 1 10 1
h 5 10 2
v 1 10 1
v 5 10 3
Sample Output 2:
4

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