vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
In this problem is used an extremely simplified version of HTML table markup. Please use the statement as a formal document and read it carefully.

A string is a bHTML table, if it satisfies the grammar: 
    
    
      
    TABLE ::= <table>ROWS</table>  
    ROWS ::= ROW | ROW ROWS  
    ROW ::= <tr>CELLS</tr>  
    CELLS ::= CELL | CELL CELLS  
    CELL ::= <td></td> | <td>TABLE</td>  
    

Blanks in the grammar are only for purposes of illustration, in the given data there will be no spaces. The bHTML table is very similar to a simple regular HTML table in which meet only the following tags : "table", "tr", "td", all the tags are paired and the table contains at least one row and at least one cell in each row. Have a look at the sample tests as examples of tables.

As can be seen, the tables may be nested. You are given a table (which may contain other(s)). You need to write a program that analyzes all the tables and finds the number of cells in each of them. The tables are not required to be rectangular.

Input

For convenience, input data can be separated into non-empty lines in an arbitrary manner. The input data consist of no more than 10 lines. Combine (concatenate) all the input lines into one, to get a text representation s of the specified table. String s corresponds to the given grammar (the root element of grammar is TABLE), its length does not exceed 5000. Only lower case letters are used to write tags. There are no spaces in the given string s.

Output

Print the sizes of all the tables in the non-decreasing order.

Examples

Input

&lt;table&gt;&lt;tr&gt;&lt;td&gt;&lt;/td&gt;&lt;/tr&gt;&lt;/table&gt;


Output

1 

Input

&lt;table&gt;
&lt;tr&gt;
&lt;td&gt;
&lt;table&gt;&lt;tr&gt;&lt;td&gt;&lt;/td&gt;&lt;/tr&gt;&lt;tr&gt;&lt;td&gt;&lt;/
td
&gt;&lt;/tr&gt;&lt;tr
&gt;&lt;td&gt;&lt;/td&gt;&lt;/tr&gt;&lt;tr&gt;&lt;td&gt;&lt;/td&gt;&lt;/tr&gt;&lt;/table&gt;
&lt;/td&gt;
&lt;/tr&gt;
&lt;/table&gt;


Output

1 4 

Input

&lt;table&gt;&lt;tr&gt;&lt;td&gt;
&lt;table&gt;&lt;tr&gt;&lt;td&gt;
&lt;table&gt;&lt;tr&gt;&lt;td&gt;
&lt;table&gt;&lt;tr&gt;&lt;td&gt;&lt;/td&gt;&lt;td&gt;&lt;/td&gt;
&lt;/tr&gt;&lt;tr&gt;&lt;td&gt;&lt;/td&gt;&lt;/tr&gt;&lt;/table&gt;
&lt;/td&gt;&lt;/tr&gt;&lt;/table&gt;
&lt;/td&gt;&lt;/tr&gt;&lt;/table&gt;
&lt;/td&gt;&lt;/tr&gt;&lt;/table&gt;


Output

1 1 1 3

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
There are *n* people taking dancing lessons. Every person is characterized by his/her dancing skill *a**i*. At the beginning of the lesson they line up from left to right. While there is at least one couple of a boy and a girl in the line, the following process is repeated: the boy and girl who stand next to each other, having the minimal difference in dancing skills start to dance. If there are several such couples, the one first from the left starts to dance. After a couple leaves to dance, the line closes again, i.e. as a result the line is always continuous. The difference in dancing skills is understood as the absolute value of difference of *a**i* variable. Your task is to find out what pairs and in what order will start dancing.

Input Specification:
The first line contains an integer *n* (1<=≤<=*n*<=≤<=2·105) — the number of people. The next line contains *n* symbols B or G without spaces. B stands for a boy, G stands for a girl. The third line contains *n* space-separated integers *a**i* (1<=≤<=*a**i*<=≤<=107) — the dancing skill. People are specified from left to right in the order in which they lined up.

Output Specification:
Print the resulting number of couples *k*. Then print *k* lines containing two numerals each — the numbers of people forming the couple. The people are numbered with integers from 1 to *n* from left to right. When a couple leaves to dance you shouldn't renumber the people. The numbers in one couple should be sorted in the increasing order. Print the couples in the order in which they leave to dance.

Demo Input:
['4\nBGBG\n4 2 4 3\n', '4\nBBGG\n4 6 1 5\n', '4\nBGBB\n1 1 2 3\n']

Demo Output:
['2\n3 4\n1 2\n', '2\n2 3\n1 4\n', '1\n1 2\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef hosts a party for his birthday. There are N people at the party. All these N people decide to play Jenga.

There are X Jenga tiles available. In one round, all the players pick 1 tile each and place it in the tower.  
The game is *valid* if:
All the players have a tile in each round;
All the tiles are used at the end.

Given N and X, find whether the game is *valid*.

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

- First line will contain T, the number of test cases. Then the test cases follow.
- Each test case contains a single line of input, containing two space-separated integers N and X representing the number of people at the party and the number of available tiles respectively.

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

For each test case, output in a single line \texttt{YES} if the game is valid, else output \texttt{NO}.

You may print each character of the string in uppercase or lowercase (for example, the strings \texttt{YeS}, \texttt{yEs}, \texttt{yes} and \texttt{YES} will all be treated as identical).

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

$1 ≤ T ≤ 10^{4}$
$1 ≤ N, X ≤ 1000$

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

----- Sample Output 1 ------ 
YES
NO
YES

----- explanation 1 ------ 
Test case $1$: The game will last for $1$ round after which the tiles will finish.

Test case $2$: There are not enough Jenga tiles for everyone to place.

Test case $3$: The game will last for $2$ rounds as after round $2$ all Jenga tiles are used.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
For a positive integer M, MoEngage defines \texttt{digitSum(M)} as the sum of digits of the number M (when written in decimal). 

For example, \texttt{digitSum(1023)} = 1 + 0 + 2 + 3 = 6.

Given a positive integer N, find the smallest integer X strictly greater than N such that:
\texttt{digitSum(N)} and \texttt{digitSum(X)} have different [parity], i.e. one of them is odd and the other is even.

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

- The first line contains an integer T, the number of test cases. The description of the T test cases follow.
- Each test case consists of a single line of input with a single integer, the number N.

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

- For each test case, print in a single line, an integer, the answer to the problem.

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

$1 ≤ T ≤ 1000$
$1 ≤ N < 10^{9}$

----- Sample Input 1 ------ 
3
123
19
509
----- Sample Output 1 ------ 
124
21
511
----- explanation 1 ------ 
Test Case $1$: $\texttt{digitSum}(123) = 1 + 2 + 3 = 6$ is even and $\texttt{digitSum}(124) = 1 + 2 + 4 = 7$ is odd, so the answer is $124$.

Test Case $2$: $\texttt{digitSum}(19) = 1 + 9 = 10$ is even, $\texttt{digitSum}(20) = 2 + 0 = 2$ is also even, whereas $\texttt{digitSum}(21) = 2 + 1 = 3$ is odd. Hence, the answer is $21$.

Test Case $3$: $\texttt{digitSum}(509) = 5 + 0 + 9 = 14$ is even, $\texttt{digitSum}(510) = 5 + 1 + 0 = 6$ is also even, whereas $\texttt{digitSum}(511) = 5 + 1 + 1 = 7$ is odd. Hence, the answer is $511$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Polo the Penguin and Strings

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Little penguin Polo adores strings. But most of all he adores strings of length *n*.

One day he wanted to find a string that meets the following conditions:
 1.  The string consists of *n* lowercase English letters (that is, the string's length equals *n*), exactly *k* of these letters are distinct. 1.  No two neighbouring letters of a string coincide; that is, if we represent a string as *s*<==<=*s*1*s*2... *s**n*, then the following inequality holds, *s**i*<=≠<=*s**i*<=+<=1(1<=≤<=*i*<=&lt;<=*n*). 1.  Among all strings that meet points 1 and 2, the required string is lexicographically smallest. 
Help him find such string or state that such string doesn't exist.

String *x*<==<=*x*1*x*2... *x**p* is lexicographically less than string *y*<==<=*y*1*y*2... *y**q*, if either *p*<=&lt;<=*q* and *x*1<==<=*y*1,<=*x*2<==<=*y*2,<=... ,<=*x**p*<==<=*y**p*, or there is such number *r* (*r*<=&lt;<=*p*,<=*r*<=&lt;<=*q*), that *x*1<==<=*y*1,<=*x*2<==<=*y*2,<=... ,<=*x**r*<==<=*y**r* and *x**r*<=+<=1<=&lt;<=*y**r*<=+<=1. The characters of the strings are compared by their ASCII codes.

Input Specification:
A single line contains two positive integers *n* and *k* (1<=≤<=*n*<=≤<=106,<=1<=≤<=*k*<=≤<=26) — the string's length and the number of distinct letters.

Output Specification:
In a single line print the required string. If there isn't such string, print "-1" (without the quotes).

Demo Input:
['7 4\n', '4 7\n']

Demo Output:
['ababacd\n', '-1\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chotu is having his mathematics test tomorrow. Chotu was solving a problem and found out that it is quite difficult for him. Given two integers A and B and some Q queries. Each query contains two numbers L and R such that L ≤ R. Find greatest number D such that L ≤ D and D ≤ R such that A and B both are divisible by D. If there is no such number answer is -1. Chotu asks your help to solve this problem as he wants to practice each and every question.

Input

The first line contains two integers A and B, the two integers as described above. 
The second line contains one integer Q, the number of queries. 
 Then Q lines follow, each line contains one query consisting of two integers, L and R.
Constraints

1 ≤ A, B ≤ 10^14
1 ≤ Q ≤ 10^6
1 ≤ L ≤ R ≤ 10^18

SAMPLE INPUT
9 27
3
1 5
6 7
8 15

SAMPLE OUTPUT
3
-1
9

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
-----Problem Statement-----
Harry Potter has one biscuit and zero rupee in his pocket. He will perform the following operations exactly $K$ times in total, in the order he likes:
- Hit his pocket, which magically increases the number of biscuits by one.
- Exchange $A$ biscuits to $1$ rupee.
- Exchange $1$ rupee to $B$ biscuits.
Find the maximum possible number of biscuits in Harry's pocket after $K$ operations.

-----Input-----
Input is given in the following format:
K A B

-----Output-----
Print the maximum possible number of biscuits in Harry's pocket after $K$operations.

-----Constraints-----
- $1 \leq K, A, B \leq 10^9$
- $K$, $A$ and  are integers.

-----Sample Input-----
4 2 6

-----Sample Output-----
7

-----EXPLANATION-----
The number of biscuits in Harry's pocket after $K$ operations is maximized as follows:
- Hit his pocket. Now he has $2$ biscuits and $0$ rupee.
- Exchange $2$ biscuits to $1$ rupee in his pocket .Now he has $0$ biscuits and $1$ rupee.
- Hit his pocket. Now he has $1$ biscuits and $1$ rupee.
- Exchange $1$ rupee to $6$ biscuits. his pocket. Now he has $7$ biscuits and $0$ rupee.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Abhishek is fond of playing cricket very much. One morning, he is playing cricket with his friends. Abhishek  is a right-hand batsman

.He has to face  all types of balls either good or  bad. There are total 26 balls in the game and each ball is represented

by one of the following two ways:-
1. "g" denotes a good ball.
2. "b" denotes a bad  ball.
All 26 balls are represented by lower case letters (a,b,.....z).
Balls faced by Abhishek are represented as a string s, all the characters of which are lower case  i.e, within  26 above mentioned balls.
A substring s[l...r] (1≤l≤r≤|s|) of string s=s1s2...s|s| (where |s| is the length of string s) is string slsl+1...sr.
The substring s[l...r] is good, if among the letters slsl+1...sr, there are at most k bad ones (refer sample explanation ).
Your task is to find out the number of distinct good substrings for the given string s. Two substrings s[x...y] and s[p...q] are considered distinct if their contents are different, i.e. s[x...y]≠s[p...q].

-----Input Format-----
First Line contains an integer T, number of test cases. For each test case, first line contains a string - a sequence of balls faced by Abhishek.

And, next line contains a string of characters "g" and "b" of length 26 characters. If the ith character of this string equals "1", then the i-th English letter is good, otherwise it's bad. That is, the first character of this string corresponds to letter "a", the second one corresponds to letter "b" and so on.

And, the third line of the test case consists of a single integer k (0≤k≤|s|) — the maximum acceptable number of bad characters in a good substring.

-----Output Format -----
For each test case, print a single integer — the number of distinct good substrings of string s.

-----Constraints-----
- 1<=T<=1000
- 1<=|s|<=2000
- 0<=k<=|s|

-----Subtasks-----
Subtask 1 : 20 Points
- 1<=T<=10
- 1<=|s|<=20
- 0<=k<=|s|
Subtask 2 : 80 Points 
Original Constraints
Sample Input
2
ababab
bgbbbbbbbbbbbbbbbbbbbbbbbb
1
acbacbacaa
bbbbbbbbbbbbbbbbbbbbbbbbbb
2
Sample Output
5
8

Explanation
In the first test case there are following good substrings: "a", "ab", "b", "ba", "bab".

In the second test case there are following good substrings: "a", "aa", "ac", "b", "ba", "c", "ca", "cb".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The Berland Forest can be represented as an infinite cell plane. Every cell contains a tree. That is, contained before the recent events.

A destructive fire raged through the Forest, and several trees were damaged by it. Precisely speaking, you have a $n \times m$ rectangle map which represents the damaged part of the Forest. The damaged trees were marked as "X" while the remaining ones were marked as ".". You are sure that all burnt trees are shown on the map. All the trees outside the map are undamaged.

The firemen quickly extinguished the fire, and now they are investigating the cause of it. The main version is that there was an arson: at some moment of time (let's consider it as $0$) some trees were set on fire. At the beginning of minute $0$, only the trees that were set on fire initially were burning. At the end of each minute, the fire spread from every burning tree to each of $8$ neighboring trees. At the beginning of minute $T$, the fire was extinguished.

The firemen want to find the arsonists as quickly as possible. The problem is, they know neither the value of $T$ (how long the fire has been raging) nor the coordinates of the trees that were initially set on fire. They want you to find the maximum value of $T$ (to know how far could the arsonists escape) and a possible set of trees that could be initially set on fire.

Note that you'd like to maximize value $T$ but the set of trees can be arbitrary.


-----Input-----

The first line contains two integer $n$ and $m$ ($1 \le n, m \le 10^6$, $1 \le n \cdot m \le 10^6$) — the sizes of the map.

Next $n$ lines contain the map. The $i$-th line corresponds to the $i$-th row of the map and contains $m$-character string. The $j$-th character of the $i$-th string is "X" if the corresponding tree is burnt and "." otherwise.

It's guaranteed that the map contains at least one "X".


-----Output-----

In the first line print the single integer $T$ — the maximum time the Forest was on fire. In the next $n$ lines print the certificate: the map ($n \times m$ rectangle) where the trees that were set on fire are marked as "X" and all other trees are marked as ".".


-----Examples-----
Input
3 6
XXXXXX
XXXXXX
XXXXXX

Output
1
......
.X.XX.
......

Input
10 10
.XXXXXX...
.XXXXXX...
.XXXXXX...
.XXXXXX...
.XXXXXXXX.
...XXXXXX.
...XXXXXX.
...XXXXXX.
...XXXXXX.
..........

Output
2
..........
..........
...XX.....
..........
..........
..........
.....XX...
..........
..........
..........

Input
4 5
X....
..XXX
..XXX
..XXX

Output
0
X....
..XXX
..XXX
..XXX

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are a mayor of Berlyatov. There are $n$ districts and $m$ two-way roads between them. The $i$-th road connects districts $x_i$ and $y_i$. The cost of travelling along this road is $w_i$. There is some path between each pair of districts, so the city is connected.

There are $k$ delivery routes in Berlyatov. The $i$-th route is going from the district $a_i$ to the district $b_i$. There is one courier on each route and the courier will always choose the cheapest (minimum by total cost) path from the district $a_i$ to the district $b_i$ to deliver products.

The route can go from the district to itself, some couriers routes can coincide (and you have to count them independently).

You can make at most one road to have cost zero (i.e. you choose at most one road and change its cost with $0$).

Let $d(x, y)$ be the cheapest cost of travel between districts $x$ and $y$.

Your task is to find the minimum total courier routes cost you can achieve, if you optimally select the some road and change its cost with $0$. In other words, you have to find the minimum possible value of $\sum\limits_{i = 1}^{k} d(a_i, b_i)$ after applying the operation described above optimally.


-----Input-----

The first line of the input contains three integers $n$, $m$ and $k$ ($2 \le n \le 1000$; $n - 1 \le m \le min(1000, \frac{n(n-1)}{2})$; $1 \le k \le 1000$) — the number of districts, the number of roads and the number of courier routes.

The next $m$ lines describe roads. The $i$-th road is given as three integers $x_i$, $y_i$ and $w_i$ ($1 \le x_i, y_i \le n$; $x_i \ne y_i$; $1 \le w_i \le 1000$), where $x_i$ and $y_i$ are districts the $i$-th road connects and $w_i$ is its cost. It is guaranteed that there is some path between each pair of districts, so the city is connected. It is also guaranteed that there is at most one road between each pair of districts.

The next $k$ lines describe courier routes. The $i$-th route is given as two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le n$) — the districts of the $i$-th route. The route can go from the district to itself, some couriers routes can coincide (and you have to count them independently).


-----Output-----

Print one integer — the minimum total courier routes cost you can achieve (i.e. the minimum value $\sum\limits_{i=1}^{k} d(a_i, b_i)$, where $d(x, y)$ is the cheapest cost of travel between districts $x$ and $y$) if you can make some (at most one) road cost zero.


-----Examples-----
Input
6 5 2
1 2 5
2 3 7
2 4 4
4 5 2
4 6 8
1 6
5 3

Output
22

Input
5 5 4
1 2 5
2 3 4
1 4 3
4 3 7
3 5 2
1 5
1 3
3 3
1 5

Output
13



-----Note-----

The picture corresponding to the first example:

[Image]

There, you can choose either the road $(2, 4)$ or the road $(4, 6)$. Both options lead to the total cost $22$.

The picture corresponding to the second example:

$A$

There, you can choose the road $(3, 4)$. This leads to the total cost $13$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You're given an array $b$ of length $n$. Let's define another array $a$, also of length $n$, for which $a_i = 2^{b_i}$ ($1 \leq i \leq n$). 

Valerii says that every two non-intersecting subarrays of $a$ have different sums of elements. You want to determine if he is wrong. More formally, you need to determine if there exist four integers $l_1,r_1,l_2,r_2$ that satisfy the following conditions:   $1 \leq l_1 \leq r_1 \lt l_2 \leq r_2 \leq n$;  $a_{l_1}+a_{l_1+1}+\ldots+a_{r_1-1}+a_{r_1} = a_{l_2}+a_{l_2+1}+\ldots+a_{r_2-1}+a_{r_2}$. 

If such four integers exist, you will prove Valerii wrong. Do they exist?

An array $c$ is a subarray of an array $d$ if $c$ can be obtained from $d$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.


-----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 line of every test case contains a single integer $n$ ($2 \le n \le 1000$).

The second line of every test case contains $n$ integers $b_1,b_2,\ldots,b_n$ ($0 \le b_i \le 10^9$). 


-----Output-----

For every test case, if there exist two non-intersecting subarrays in $a$ that have the same sum, output YES on a separate line. Otherwise, output NO on a separate line. 

Also, note that each letter can be in any case. 


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

Output
YES
NO



-----Note-----

In the first case, $a = [16,8,1,2,4,1]$. Choosing $l_1 = 1$, $r_1 = 1$, $l_2 = 2$ and $r_2 = 6$ works because $16 = (8+1+2+4+1)$.

In the second case, you can verify that there is no way to select to such subarrays.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let's assume that set S consists of m distinct intervals [l1, r1], [l2, r2], ..., [lm, rm] (1 ≤ li ≤ ri ≤ n; li, ri are integers).

Let's assume that f(S) is the maximum number of intervals that you can choose from the set S, such that every two of them do not intersect. We assume that two intervals, [l1, r1] and [l2, r2], intersect if there is an integer x, which meets two inequalities: l1 ≤ x ≤ r1 and l2 ≤ x ≤ r2.

Sereja wonders, how many sets S are there, such that f(S) = k? Count this number modulo 1000000007 (109 + 7).

Input

The first line contains integers n, k (1 ≤ n ≤ 500; 0 ≤ k ≤ 500).

Output

In a single line, print the answer to the problem modulo 1000000007 (109 + 7).

Examples

Input

3 1


Output

23


Input

3 2


Output

32


Input

2 0


Output

1


Input

2 2


Output

2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You came across this story while reading a book. Long a ago when the modern entertainment systems did not exist people used to go to watch plays in theaters, where people would perform live in front of an audience. There was a beautiful actress who had a disability she could not pronounce the character $'r'$. To win her favours which many have been denied in past, you decide to write a whole play without the character $'r'$. Now you have to get the script reviewed by the editor before presenting it to her.
The editor was flattered by the script and agreed to you to proceed. The editor will edit the script in this way to suit her style. For each word replace it with a sub-sequence of itself such that it contains the character 'a'. 
A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements Wikipedia 
Now given a script with $N$ words, for each word in the script you wish to know the number of subsequences with which it can be replaced. 

-----Input:-----
- First-line will contain $N$, the number of words in the script. Then next $N$ line with one test case each. 
- Each test case contains a single word $W_i$

-----Output:-----
For each test case, output in a single line number of subsequences with which it can be replaced. 

-----Constraints-----
- $1 \leq N \leq 1000$
- $1 \leq$ length of $W_i$  $\leq 20$
- $W_i$  on contains lowercase english alphabets and does not have the character 'r'

-----Sample Input 1:-----
2
abc
aba

-----Sample Output 1:-----
4
6

-----EXPLANATION:-----
This subsequences with which $abc$ can be replaed : ${a,ab,ac,abc}$. 
This subsequences with which $aba$ can be replaed : ${a,ab,aba,a,ba,a}$. 

-----Sample Input 2:-----
3
abcde
abcdea
xyz

-----Sample Output 2:-----
16
48
0

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