meetforever/GRPO_CL huggingface dataset:
user: You are given an integer m.

Let M = 2^{m} - 1.

You are also given a set of n integers denoted as the set T. The integers will be provided in base 2 as n binary strings of length m.

A set of integers S is called "good" if the following hold.   If $a \in S$, then [Image].  If $a, b \in S$, then $a \text{AND} b \in S$  $T \subseteq S$  All elements of S are less than or equal to M. 

Here, $XOR$ and $\text{AND}$ refer to the bitwise XOR and bitwise AND operators, respectively.

Count the number of good sets S, modulo 10^9 + 7.


-----Input-----

The first line will contain two integers m and n (1 ≤ m ≤ 1 000, 1 ≤ n ≤ min(2^{m}, 50)).

The next n lines will contain the elements of T. Each line will contain exactly m zeros and ones. Elements of T will be distinct.


-----Output-----

Print a single integer, the number of good sets modulo 10^9 + 7. 


-----Examples-----
Input
5 3
11010
00101
11000

Output
4

Input
30 2
010101010101010010101010101010
110110110110110011011011011011

Output
860616440



-----Note-----

An example of a valid set S is {00000, 00101, 00010, 00111, 11000, 11010, 11101, 11111}.
user: You might have remembered Theatre square from the problem 1A. Now it's finally getting repaved.

The square still has a rectangular shape of $n \times m$ meters. However, the picture is about to get more complicated now. Let $a_{i,j}$ be the $j$-th square in the $i$-th row of the pavement.

You are given the picture of the squares:  if $a_{i,j} = $ "*", then the $j$-th square in the $i$-th row should be black;  if $a_{i,j} = $ ".", then the $j$-th square in the $i$-th row should be white. 

The black squares are paved already. You have to pave the white squares. There are two options for pavement tiles:  $1 \times 1$ tiles — each tile costs $x$ burles and covers exactly $1$ square;  $1 \times 2$ tiles — each tile costs $y$ burles and covers exactly $2$ adjacent squares of the same row. Note that you are not allowed to rotate these tiles or cut them into $1 \times 1$ tiles. 

You should cover all the white squares, no two tiles should overlap and no black squares should be covered by tiles.

What is the smallest total price of the tiles needed to cover all the white squares?


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 500$) — the number of testcases. Then the description of $t$ testcases follow.

The first line of each testcase contains four integers $n$, $m$, $x$ and $y$ ($1 \le n \le 100$; $1 \le m \le 1000$; $1 \le x, y \le 1000$) — the size of the Theatre square, the price of the $1 \times 1$ tile and the price of the $1 \times 2$ tile.

Each of the next $n$ lines contains $m$ characters. The $j$-th character in the $i$-th line is $a_{i,j}$. If $a_{i,j} = $ "*", then the $j$-th square in the $i$-th row should be black, and if $a_{i,j} = $ ".", then the $j$-th square in the $i$-th row should be white.

It's guaranteed that the sum of $n \times m$ over all testcases doesn't exceed $10^5$.


-----Output-----

For each testcase print a single integer — the smallest total price of the tiles needed to cover all the white squares in burles.


-----Example-----
Input
4
1 1 10 1
.
1 2 10 1
..
2 1 10 1
.
.
3 3 3 7
..*
*..
.*.

Output
10
1
20
18



-----Note-----

In the first testcase you are required to use a single $1 \times 1$ tile, even though $1 \times 2$ tile is cheaper. So the total price is $10$ burles.

In the second testcase you can either use two $1 \times 1$ tiles and spend $20$ burles or use a single $1 \times 2$ tile and spend $1$ burle. The second option is cheaper, thus the answer is $1$.

The third testcase shows that you can't rotate $1 \times 2$ tiles. You still have to use two $1 \times 1$ tiles for the total price of $20$.

In the fourth testcase the cheapest way is to use $1 \times 1$ tiles everywhere. The total cost is $6 \cdot 3 = 18$.
user: You are looking at the floor plan of the Summer Informatics School's new building. You were tasked with SIS logistics, so you really care about travel time between different locations: it is important to know how long it would take to get from the lecture room to the canteen, or from the gym to the server room.

The building consists of n towers, h floors each, where the towers are labeled from 1 to n, the floors are labeled from 1 to h. There is a passage between any two adjacent towers (two towers i and i + 1 for all i: 1 ≤ i ≤ n - 1) on every floor x, where a ≤ x ≤ b. It takes exactly one minute to walk between any two adjacent floors of a tower, as well as between any two adjacent towers, provided that there is a passage on that floor. It is not permitted to leave the building.

 [Image]

The picture illustrates the first example. 

You have given k pairs of locations (t_{a}, f_{a}), (t_{b}, f_{b}): floor f_{a} of tower t_{a} and floor f_{b} of tower t_{b}. For each pair you need to determine the minimum walking time between these locations.


-----Input-----

The first line of the input contains following integers:

  n: the number of towers in the building (1 ≤ n ≤ 10^8),  h: the number of floors in each tower (1 ≤ h ≤ 10^8),  a and b: the lowest and highest floor where it's possible to move between adjacent towers (1 ≤ a ≤ b ≤ h),  k: total number of queries (1 ≤ k ≤ 10^4). 

Next k lines contain description of the queries. Each description consists of four integers t_{a}, f_{a}, t_{b}, f_{b} (1 ≤ t_{a}, t_{b} ≤ n, 1 ≤ f_{a}, f_{b} ≤ h). This corresponds to a query to find the minimum travel time between f_{a}-th floor of the t_{a}-th tower and f_{b}-th floor of the t_{b}-th tower.


-----Output-----

For each query print a single integer: the minimum walking time between the locations in minutes.


-----Example-----
Input
3 6 2 3 3
1 2 1 3
1 4 3 4
1 2 2 3

Output
1
4
2
user: A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array) and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

For a positive integer $n$, we call a permutation $p$ of length $n$ good if the following condition holds for every pair $i$ and $j$ ($1 \le i \le j \le n$) —   $(p_i \text{ OR } p_{i+1} \text{ OR } \ldots \text{ OR } p_{j-1} \text{ OR } p_{j}) \ge j-i+1$, where $\text{OR}$ denotes the bitwise OR operation. 

In other words, a permutation $p$ is good if for every subarray of $p$, the $\text{OR}$ of all elements in it is not less than the number of elements in that subarray. 

Given a positive integer $n$, output any good permutation of length $n$. We can show that for the given constraints such a permutation always exists.


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). Description of the test cases follows.

The first and only line of every test case contains a single integer $n$ ($1 \le n \le 100$).


-----Output-----

For every test, output any good permutation of length $n$ on a separate line. 


-----Example-----
Input
3
1
3
7

Output
1
3 1 2
4 3 5 2 7 1 6



-----Note-----

For $n = 3$, $[3,1,2]$ is a good permutation. Some of the subarrays are listed below.   $3\text{ OR }1 = 3 \geq 2$ $(i = 1,j = 2)$  $3\text{ OR }1\text{ OR }2 = 3 \geq 3$ $(i = 1,j = 3)$  $1\text{ OR }2 = 3 \geq 2$ $(i = 2,j = 3)$  $1 \geq 1$ $(i = 2,j = 2)$ 

Similarly, you can verify that $[4,3,5,2,7,1,6]$ is also good.
user: You are given $n$ segments on a coordinate line; each endpoint of every segment has integer coordinates. Some segments can degenerate to points. Segments can intersect with each other, be nested in each other or even coincide.

Your task is the following: for every $k \in [1..n]$, calculate the number of points with integer coordinates such that the number of segments that cover these points equals $k$. A segment with endpoints $l_i$ and $r_i$ covers point $x$ if and only if $l_i \le x \le r_i$.


-----Input-----

The first line of the input contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of segments.

The next $n$ lines contain segments. The $i$-th line contains a pair of integers $l_i, r_i$ ($0 \le l_i \le r_i \le 10^{18}$) — the endpoints of the $i$-th segment.


-----Output-----

Print $n$ space separated integers $cnt_1, cnt_2, \dots, cnt_n$, where $cnt_i$ is equal to the number of points such that the number of segments that cover these points equals to $i$.


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

Output
6 2 1 

Input
3
1 3
2 4
5 7

Output
5 2 0 



-----Note-----

The picture describing the first example:

[Image]

Points with coordinates $[0, 4, 5, 6, 7, 8]$ are covered by one segment, points $[1, 2]$ are covered by two segments and point $[3]$ is covered by three segments.

The picture describing the second example:

[Image]

Points $[1, 4, 5, 6, 7]$ are covered by one segment, points $[2, 3]$ are covered by two segments and there are no points covered by three segments.
user: John has just bought a new car and is planning a journey around the country. Country has N cities, some of which are connected by bidirectional roads. There are N - 1 roads and every city is reachable from any other city. Cities are labeled from 1 to N.

John first has to select from which city he will start his journey. After that, he spends one day in a city and then travels to a randomly choosen city which is directly connected to his current one and which he has not yet visited. He does this until he can't continue obeying these rules.

To select the starting city, he calls his friend Jack for advice. Jack is also starting a big casino business and wants to open casinos in some of the cities (max 1 per city, maybe nowhere). Jack knows John well and he knows that if he visits a city with a casino, he will gamble exactly once before continuing his journey.

He also knows that if John enters a casino in a good mood, he will leave it in a bad mood and vice versa. Since he is John's friend, he wants him to be in a good mood at the moment when he finishes his journey. John is in a good mood before starting the journey.

In how many ways can Jack select a starting city for John and cities where he will build casinos such that no matter how John travels, he will be in a good mood at the end? Print answer modulo 10^9 + 7.


-----Input-----

In the first line, a positive integer N (1 ≤ N ≤ 100000), the number of cities. 

In the next N - 1 lines, two numbers a,  b (1 ≤ a, b ≤ N) separated by a single space meaning that cities a and b are connected by a bidirectional road.


-----Output-----

Output one number, the answer to the problem modulo 10^9 + 7.


-----Examples-----
Input
2
1 2

Output
4

Input
3
1 2
2 3

Output
10



-----Note-----

Example 1: If Jack selects city 1 as John's starting city, he can either build 0 casinos, so John will be happy all the time, or build a casino in both cities, so John would visit a casino in city 1, become unhappy, then go to city 2, visit a casino there and become happy and his journey ends there because he can't go back to city 1. If Jack selects city 2 for start, everything is symmetrical, so the answer is 4.

Example 2: If Jack tells John to start from city 1, he can either build casinos in 0 or 2 cities (total 4 possibilities). If he tells him to start from city 2, then John's journey will either contain cities 2 and 1 or 2 and 3. Therefore, Jack will either have to build no casinos, or build them in all three cities. With other options, he risks John ending his journey unhappy. Starting from 3 is symmetric to starting from 1, so in total we have 4 + 2 + 4 = 10 options.
user: There always is something to choose from! And now, instead of "Noughts and Crosses", Inna choose a very unusual upgrade of this game. The rules of the game are given below:

There is one person playing the game. Before the beginning of the game he puts 12 cards in a row on the table. Each card contains a character: "X" or "O". Then the player chooses two positive integers a and b (a·b = 12), after that he makes a table of size a × b from the cards he put on the table as follows: the first b cards form the first row of the table, the second b cards form the second row of the table and so on, the last b cards form the last (number a) row of the table. The player wins if some column of the table contain characters "X" on all cards. Otherwise, the player loses.

Inna has already put 12 cards on the table in a row. But unfortunately, she doesn't know what numbers a and b to choose. Help her win the game: print to her all the possible ways of numbers a, b that she can choose and win.


-----Input-----

The first line of the input contains integer t (1 ≤ t ≤ 100). This value shows the number of sets of test data in the input. Next follows the description of each of the t tests on a separate line.

The description of each test is a string consisting of 12 characters, each character is either "X", or "O". The i-th character of the string shows the character that is written on the i-th card from the start.


-----Output-----

For each test, print the answer to the test on a single line. The first number in the line must represent the number of distinct ways to choose the pair a, b. Next, print on this line the pairs in the format axb. Print the pairs in the order of increasing first parameter (a). Separate the pairs in the line by whitespaces.


-----Examples-----
Input
4
OXXXOXOOXOOX
OXOXOXOXOXOX
XXXXXXXXXXXX
OOOOOOOOOOOO

Output
3 1x12 2x6 4x3
4 1x12 2x6 3x4 6x2
6 1x12 2x6 3x4 4x3 6x2 12x1
0
user: A competitive eater, Alice is scheduling some practices for an eating contest on a magical calendar. The calendar is unusual because a week contains not necessarily $7$ days!

In detail, she can choose any integer $k$ which satisfies $1 \leq k \leq r$, and set $k$ days as the number of days in a week.

Alice is going to paint some $n$ consecutive days on this calendar. On this calendar, dates are written from the left cell to the right cell in a week. If a date reaches the last day of a week, the next day's cell is the leftmost cell in the next (under) row.

She wants to make all of the painted cells to be connected by side. It means, that for any two painted cells there should exist at least one sequence of painted cells, started in one of these cells, and ended in another, such that any two consecutive cells in this sequence are connected by side.

Alice is considering the shape of the painted cells. Two shapes are the same if there exists a way to make them exactly overlapped using only parallel moves, parallel to the calendar's sides.

For example, in the picture, a week has $4$ days and Alice paints $5$ consecutive days. [1] and [2] are different shapes, but [1] and [3] are equal shapes. [Image] 

Alice wants to know how many possible shapes exists if she set how many days a week has and choose consecutive $n$ days and paints them in calendar started in one of the days of the week. As was said before, she considers only shapes, there all cells are connected by side.


-----Input-----

The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases. Next $t$ lines contain descriptions of test cases.

For each test case, the only line contains two integers $n$, $r$ ($1 \le n \le 10^9, 1 \le r \le 10^9$).


-----Output-----

For each test case, print a single integer  — the answer to the problem.

Please note, that the answer for some test cases won't fit into $32$-bit integer type, so you should use at least $64$-bit integer type in your programming language.


-----Example-----
Input
5
3 4
3 2
3 1
13 7
1010000 9999999

Output
4
3
1
28
510049495001



-----Note-----

In the first test case, Alice can set $1,2,3$ or $4$ days as the number of days in a week.

There are $6$ possible paintings shown in the picture, but there are only $4$ different shapes. So, the answer is $4$. Notice that the last example in the picture is an invalid painting because all cells are not connected by sides. [Image] 

In the last test case, be careful with the overflow issue, described in the output format.
user: Nastya just made a huge mistake and dropped a whole package of rice on the floor. Mom will come soon. If she sees this, then Nastya will be punished.

In total, Nastya dropped $n$ grains. Nastya read that each grain weighs some integer number of grams from $a - b$ to $a + b$, inclusive (numbers $a$ and $b$ are known), and the whole package of $n$ grains weighs from $c - d$ to $c + d$ grams, inclusive (numbers $c$ and $d$ are known). The weight of the package is the sum of the weights of all $n$ grains in it.

Help Nastya understand if this information can be correct. In other words, check whether each grain can have such a mass that the $i$-th grain weighs some integer number $x_i$ $(a - b \leq x_i \leq a + b)$, and in total they weigh from $c - d$ to $c + d$, inclusive ($c - d \leq \sum\limits_{i=1}^{n}{x_i} \leq c + d$).


-----Input-----

The input consists of multiple test cases. The first line contains a single integer $t$ $(1 \leq t \leq 1000)$  — the number of test cases. 

The next $t$ lines contain descriptions of the test cases, each line contains $5$ integers: $n$ $(1 \leq n \leq 1000)$  — the number of grains that Nastya counted and $a, b, c, d$ $(0 \leq b < a \leq 1000, 0 \leq d < c \leq 1000)$  — numbers that determine the possible weight of one grain of rice (from $a - b$ to $a + b$) and the possible total weight of the package (from $c - d$ to $c + d$).


-----Output-----

For each test case given in the input print "Yes", if the information about the weights is not inconsistent, and print "No" if $n$ grains with masses from $a - b$ to $a + b$ cannot make a package with a total mass from $c - d$ to $c + d$.


-----Example-----
Input
5
7 20 3 101 18
11 11 10 234 2
8 9 7 250 122
19 41 21 321 10
3 10 8 6 1

Output
Yes
No
Yes
No
Yes



-----Note-----

In the first test case of the example, we can assume that each grain weighs $17$ grams, and a pack $119$ grams, then really Nastya could collect the whole pack.

In the third test case of the example, we can assume that each grain weighs $16$ grams, and a pack $128$ grams, then really Nastya could collect the whole pack.

In the fifth test case of the example, we can be assumed that $3$ grains of rice weigh $2$, $2$, and $3$ grams, and a pack is $7$ grams, then really Nastya could collect the whole pack.

In the second and fourth test cases of the example, we can prove that it is impossible to determine the correct weight of all grains of rice and the weight of the pack so that the weight of the pack is equal to the total weight of all collected grains.
user: We saw the little game Marmot made for Mole's lunch. Now it's Marmot's dinner time and, as we all know, Marmot eats flowers. At every dinner he eats some red and white flowers. Therefore a dinner can be represented as a sequence of several flowers, some of them white and some of them red.

But, for a dinner to be tasty, there is a rule: Marmot wants to eat white flowers only in groups of size k.

Now Marmot wonders in how many ways he can eat between a and b flowers. As the number of ways could be very large, print it modulo 1000000007 (10^9 + 7).


-----Input-----

Input contains several test cases.

The first line contains two integers t and k (1 ≤ t, k ≤ 10^5), where t represents the number of test cases.

The next t lines contain two integers a_{i} and b_{i} (1 ≤ a_{i} ≤ b_{i} ≤ 10^5), describing the i-th test.


-----Output-----

Print t lines to the standard output. The i-th line should contain the number of ways in which Marmot can eat between a_{i} and b_{i} flowers at dinner modulo 1000000007 (10^9 + 7).


-----Examples-----
Input
3 2
1 3
2 3
4 4

Output
6
5
5



-----Note-----  For K = 2 and length 1 Marmot can eat (R).  For K = 2 and length 2 Marmot can eat (RR) and (WW).  For K = 2 and length 3 Marmot can eat (RRR), (RWW) and (WWR).  For K = 2 and length 4 Marmot can eat, for example, (WWWW) or (RWWR), but for example he can't eat (WWWR).
user: You are given an array a of size n, and q queries to it. There are queries of two types:   1 l_{i} r_{i} — perform a cyclic shift of the segment [l_{i}, r_{i}] to the right. That is, for every x such that l_{i} ≤ x < r_{i} new value of a_{x} + 1 becomes equal to old value of a_{x}, and new value of a_{l}_{i} becomes equal to old value of a_{r}_{i};  2 l_{i} r_{i} — reverse the segment [l_{i}, r_{i}].  

There are m important indices in the array b_1, b_2, ..., b_{m}. For each i such that 1 ≤ i ≤ m you have to output the number that will have index b_{i} in the array after all queries are performed.


-----Input-----

The first line contains three integer numbers n, q and m (1 ≤ n, q ≤ 2·10^5, 1 ≤ m ≤ 100). 

The second line contains n integer numbers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9). 

Then q lines follow. i-th of them contains three integer numbers t_{i}, l_{i}, r_{i}, where t_{i} is the type of i-th query, and [l_{i}, r_{i}] is the segment where this query is performed (1 ≤ t_{i} ≤ 2, 1 ≤ l_{i} ≤ r_{i} ≤ n). 

The last line contains m integer numbers b_1, b_2, ..., b_{m} (1 ≤ b_{i} ≤ n) — important indices of the array. 


-----Output-----

Print m numbers, i-th of which is equal to the number at index b_{i} after all queries are done.


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

Output
3 3 1 5 2
user: Palo Alto is an unusual city because it is an endless coordinate line. It is also known for the office of Lyft Level 5.

Lyft has become so popular so that it is now used by all $m$ taxi drivers in the city, who every day transport the rest of the city residents — $n$ riders.

Each resident (including taxi drivers) of Palo-Alto lives in its unique location (there is no such pair of residents that their coordinates are the same).

The Lyft system is very clever: when a rider calls a taxi, his call does not go to all taxi drivers, but only to the one that is the closest to that person. If there are multiple ones with the same distance, then to taxi driver with a smaller coordinate is selected.

But one morning the taxi drivers wondered: how many riders are there that would call the given taxi driver if they were the first to order a taxi on that day? In other words, you need to find for each taxi driver $i$ the number $a_{i}$ — the number of riders that would call the $i$-th taxi driver when all drivers and riders are at their home?

The taxi driver can neither transport himself nor other taxi drivers.


-----Input-----

The first line contains two integers $n$ and $m$ ($1 \le n,m \le 10^5$) — number of riders and taxi drivers.

The second line contains $n + m$ integers $x_1, x_2, \ldots, x_{n+m}$ ($1 \le x_1 < x_2 < \ldots < x_{n+m} \le 10^9$), where $x_i$ is the coordinate where the $i$-th resident lives. 

The third line contains $n + m$ integers $t_1, t_2, \ldots, t_{n+m}$ ($0 \le t_i \le 1$). If $t_i = 1$, then the $i$-th resident is a taxi driver, otherwise $t_i = 0$.

It is guaranteed that the number of $i$ such that $t_i = 1$ is equal to $m$.


-----Output-----

Print $m$ integers $a_1, a_2, \ldots, a_{m}$, where $a_i$ is the answer for the $i$-th taxi driver. The taxi driver has the number $i$ if among all the taxi drivers he lives in the $i$-th smallest coordinate (see examples for better understanding).


-----Examples-----
Input
3 1
1 2 3 10
0 0 1 0

Output
3 
Input
3 2
2 3 4 5 6
1 0 0 0 1

Output
2 1 
Input
1 4
2 4 6 10 15
1 1 1 1 0

Output
0 0 0 1 


-----Note-----

In the first example, we have only one taxi driver, which means an order from any of $n$ riders will go to him.

In the second example, the first taxi driver lives at the point with the coordinate $2$, and the second one lives at the point with the coordinate $6$. Obviously, the nearest taxi driver to the rider who lives on the $3$ coordinate is the first one, and to the rider who lives on the coordinate $5$ is the second one. The rider who lives on the $4$ coordinate has the same distance to the first and the second taxi drivers, but since the first taxi driver has a smaller coordinate, the call from this rider will go to the first taxi driver.

In the third example, we have one rider and the taxi driver nearest to him is the fourth one.