vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
The only difference between the easy and the hard versions is constraints.

A subsequence is a string that can be derived from another string by deleting some or no symbols without changing the order of the remaining symbols. Characters to be deleted are not required to go successively, there can be any gaps between them. For example, for the string "abaca" the following strings are subsequences: "abaca", "aba", "aaa", "a" and "" (empty string). But the following strings are not subsequences: "aabaca", "cb" and "bcaa".

You are given a string $s$ consisting of $n$ lowercase Latin letters.

In one move you can take any subsequence $t$ of the given string and add it to the set $S$. The set $S$ can't contain duplicates. This move costs $n - |t|$, where $|t|$ is the length of the added subsequence (i.e. the price equals to the number of the deleted characters).

Your task is to find out the minimum possible total cost to obtain a set $S$ of size $k$ or report that it is impossible to do so.


-----Input-----

The first line of the input contains two integers $n$ and $k$ ($1 \le n, k \le 100$) — the length of the string and the size of the set, correspondingly.

The second line of the input contains a string $s$ consisting of $n$ lowercase Latin letters.


-----Output-----

Print one integer — if it is impossible to obtain the set $S$ of size $k$, print -1. Otherwise, print the minimum possible total cost to do it.


-----Examples-----
Input
4 5
asdf

Output
4

Input
5 6
aaaaa

Output
15

Input
5 7
aaaaa

Output
-1

Input
10 100
ajihiushda

Output
233



-----Note-----

In the first example we can generate $S$ = { "asdf", "asd", "adf", "asf", "sdf" }. The cost of the first element in $S$ is $0$ and the cost of the others is $1$. So the total cost of $S$ is $4$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider the number `1176` and its square (`1176 * 1176) = 1382976`. Notice that:

* the first two digits of `1176` form a prime.
* the first two digits of the square `1382976` also form a prime.
* the last two digits of `1176` and `1382976` are the same. 

Given two numbers representing a range (`a, b`), how many numbers satisfy this property within that range? (`a <= n < b`)


## Example

`solve(2, 1200) = 1`, because only `1176` satisfies this property within the range `2 <= n < 1200`. See test cases for more examples. The upper bound for the range will not exceed `1,000,000`. 

Good luck!

If you like this Kata, please try:

[Simple Prime Streaming](https://www.codewars.com/kata/5a908da30025e995880000e3)

[Alphabet symmetry](https://www.codewars.com/kata/59d9ff9f7905dfeed50000b0)

[Upside down numbers](https://www.codewars.com/kata/59f7597716049833200001eb)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Misha has a tree with characters written on the vertices. He can choose two vertices s and t of this tree and write down characters of vertices lying on a path from s to t. We'll say that such string corresponds to pair (s, t).

Misha has m queries of type: you are given 4 vertices a, b, c, d; you need to find the largest common prefix of the strings that correspond to pairs (a, b) and (c, d). Your task is to help him.

Input

The first line contains integer n (1 ≤ n ≤ 300 000) — the number of vertices in the tree.

Next follows a line consisting of n small English letters. The i-th character of the string corresponds to the character written on the i-th vertex. 

Next n - 1 lines contain information about edges. An edge is defined by a pair of integers u, v (1 ≤ u, v ≤ n, u ≠ v), separated by spaces.

The next line contains integer m (1 ≤ m ≤ 1 000 000) — the number of queries.

Next m lines contain information about queries. A query is defined by four integers a, b, c, d (1 ≤ a, b, c, d ≤ n), separated by spaces.

Output

For each query print the length of the largest common prefix on a separate line.

Examples

Input

6
bbbabb
2 1
3 2
4 3
5 2
6 5
6
2 5 3 1
1 5 2 3
5 6 5 6
6 3 4 1
6 2 3 4
2 2 4 5


Output

2
2
2
0
1
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
It is Greg’s birthday! To celebrate, his friend Sam invites Greg and two other friends for a small party. Of course, every birthday party must have cake.

Sam ordered a square cake. She makes a single horizontal cut and a single vertical cut. In her excitement to eat cake, Sam forgot to make these cuts through the middle of the cake.

Of course, the biggest piece of cake should go to Greg since it is his birthday. Help Sam determine the volume of the biggest piece of cake that resulted from these two cuts.

-----Input-----
The input consists of a single line containing three integers $n$ ($2 \leq n \leq 10000$), the length of the sides of the square cake in centimeters, $h$ ($0 < h < n$), the distance of the horizontal cut from the top edge of the cake in centimeters, and $v$ ($0 < v < n$), the distance of the vertical cut from the left edge of the cake in centimeters. This is illustrated in the figure above.

Each cake is $4$ centimeters thick.

-----Output-----
Display the volume (in cubic centimeters) of the largest of the four pieces of cake after the horizontal and vertical cuts are made.

-----Examples-----
Sample Input 1:
10 4 7
Sample Output 1:
168

Sample Input 2:
5 2 2
Sample Output 2:
36

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Gematria is an Assyro-Babylonian-Greek system of code and numerology later adopted into Jewish culture. The system assigns numerical value to a word or a phrase in the belief that words or phrases with identical numerical values bear some relation to each other or bear some relation to the number itself. While more commonly used on Hebrew words, there is also an English version.

Each letter has a value and the gematrian value of a word or a phrase is the sum of those values. The code takes a word or an expression and returns the gematrian value of it.

The calculation is case insensitive and counts no spaces. 

Example: The gematrian value of "love" is 20+50+700+5 = 775

‎These are the values of the different letters:

a=1, b=2, c=3, d=4, e=5, f=6, g=7, h=8, i=9, k=10, l=20,
m=30, n=40, o=50, p=60, q=70, r=80, s=90, t=100, u=200,
x=300, y=400, z=500, j=600, v=700, w=900

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Suppose there is a X x Y x Z 3D matrix A of numbers having coordinates (i, j, k) where 0 ≤ i < X, 0 ≤ j < Y, 0 ≤ k < Z. Now another X x Y x Z matrix B is defined from A such that the (i, j, k) element of B is the sum of all the the numbers in A in the cuboid defined by the (0, 0, 0) and (i, j, k) elements as the diagonally opposite vertices. In other word (i, j, k) in B is the sum of numbers of A having coordinates (a, b, c) such that 0 ≤ a ≤ i, 0 ≤ b ≤ j, 0 ≤ c ≤ k. The problem is that given B, you have to find out A.

Input
The first line of input will contain the number of test cases ( ≤ 10). That many test cases will follow in subsequent lines. The first line of each test case will contain the numbers X Y Z (0 ≤ X, Y, Z ≤ 100). After that there will be X x Y lines each containing Z numbers of B. The first line contains the numbers (0, 0, 0), (0, 0, 1)..., (0, 0, Z-1). The second line has the numbers (0, 1, 0), (0, 1, 1)..., (0, 1, Z-1) and so on. The (Y+1)^th line will have the numbers (1, 0, 0), (1, 0, 1)..., (1, 0, Z-1) and so on.

Output
For each test case print the numbers of A in exactly the same fashion as the input.

Example

Input:
2
3 1 1
1 
8 
22 
1 2 3
0 9 13 
18 45 51 

Output:
1 
7 
14 
0 9 4 
18 18 2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
.task {
  background: #fff;
  color: #333;
  padding: 25px;
  box-sizing: border-box;
  font-family: Comfortaa, sans-serif !important;
  position: relative;
}
.task code, .task_code {
  display: inline-block;
  padding: 0;
  border-radius: 2px;
  margin: 0;
  position: relative;
  top: 6px;
  background: bisque;
  border: 1px solid #f9d2a4;
  padding: 3px;
  line-height: 1em;
}
.task_code {
  top: -1px;
}
.task_header {
  color: #333 !important;
  margin-top: 0;
  font-size: 30px !important;
}
.task_inner {
  box-shadow: 0 2px 11px -3px rgba(0,0,0,.6);
  padding: 20px;
  border-radius: 3px;
}
.task_devil {
  float: right;
  margin-left: 15px;
  shape-outside: circle(150px);
}
.task_devil img {
  max-width: 150px;
}
.task_part-header { 
  font-size: 20px !important;
  font-weight: 800;
  color: #333;
  padding: 20px 0 10px;
}
.task_part-header:first-of-type {
  padding-top: 0;
}
.task_list {
  padding: 0;
  margin: 10px 0;
  padding-left: 30px;
}
.task_list ul {
  padding: 0;
  margin: 0;
}
.font-effect-canvas-print { color: black; }


Devil's Sequence

Problem



    Robodevil likes to do some mathematics between rehearsals of his orchestra. Today he invented devilish sequence No. 1729:
    

x0 = 0,
x1 = 1,
xn = (xn - 1 + xn - 2) / 2.


    For example, x10 = 0.666015625. Robodevil became interested at once how many `sixes` there were at the beginning of an arbitrary xn. In 6 nanoseconds, he had a formula. Can you do the same?
    Input
    You are given an integer n; `2 ≤ n ≤ 100000`.
    Output
    Output the number of sixes at the beginning of xn in decimal notation.
    Example



Input
Output


10
3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: The Smallest String Concatenation

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You're given a list of *n* strings *a*1,<=*a*2,<=...,<=*a**n*. You'd like to concatenate them together in some order such that the resulting string would be lexicographically smallest.

Given the list of strings, output the lexicographically smallest concatenation.

Input Specification:
The first line contains integer *n* — the number of strings (1<=≤<=*n*<=≤<=5·104).

Each of the next *n* lines contains one string *a**i* (1<=≤<=|*a**i*|<=≤<=50) consisting of only lowercase English letters. The sum of string lengths will not exceed 5·104.

Output Specification:
Print the only string *a* — the lexicographically smallest string concatenation.

Demo Input:
['4\nabba\nabacaba\nbcd\ner\n', '5\nx\nxx\nxxa\nxxaa\nxxaaa\n', '3\nc\ncb\ncba\n']

Demo Output:
['abacabaabbabcder\n', 'xxaaaxxaaxxaxxx\n', 'cbacbc\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given three integers a, b and c. The task is to check if it is possible to make right angled triangle with sides of length a, b and c.
 
Example 1:
Input:
a = 3, b = 4, c = 5
Output:
Yes
Explanation:
We can form a right angled triangle
with sides of length 3, 4 and 5.
Example 2:
Input:
a = 2, b = 5, c = 8
Output:
No
Explanation:
We can't form a right angled triangle
with sides of length 2, 5 and 8.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function rightAngTri() which takes 3 Integers a,b and c as input and returns "Yes" if it is possible to form a right angled triangle with sides of length a, b, and c, else return "No".
 
Expected Time Complexity: O(log(max(a,b,c)))
Expected Auxiliary Space: O(1)
 
Constraints:
1 <= a,b,c <= 10^{8}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Pandaland is a country & has N cities inside it. The cities are numbered from 1 to N. There are N-1 roads connecting these cities. We can reach a city from another city from a unique path(sequence of roads). Each road is of length 1 unit. 
Panda lives in a city called bambooland, but his bro, Rishi, due to some circumstances lives in a different city called thugland. Now, Panda wants to hangout with Rishi as they are bros. Unfortunately, they get to know that the distance between their cities is the maximum in Pandaland, i.e. no two cities in Pandaland have distance greater than that between bambooland and thugland. So, Panda needs to know the distance he has to travel to meet his bro Rishi.
Help him out to find the distance between bambooland and thugland. 

INPUT:

First line of Input contains an Integer N.

Next N-1 lines contains two space-separated integers X,Y denoting there exists a road between X & Y.

OUTPUT:

Print the answer in a Single line.

Constraints:

1<N ≤ 10^5

1 ≤ X,Y ≤ N

Problem Author: Rishi Kundu & Gaurav Sharma

SAMPLE INPUT
4
1 2
1 3
1 4

SAMPLE OUTPUT
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given coordinates of four points in a plane. Find if the four points form a square or not.
Example 1:
Input:
points=(0,0),(0,1),(1,0),(1,1)
Output:
1
Explanation:
These points form a square.
Example 2:
Input:
points=(0,0),(1,1),(1,0),(0,2)
Output:
0
Explanation:
These four points do not form a square.
Your Task:
You don't need to read input or print anything.Your Task is to complete the function fourPointSquare() which takes a 2D array of dimensions 4x2 which contains the cordinates of the four points and returns 1 if they form a square.Otherwise it returns 0.
 
Expected Time Complexity:O(1)
Expected Space Complexity:O(1)
 
Constraints:
0<=X-cordinate,Y-cordinate<=10^{5}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
H: About Our Effort-About Our Effort-

problem

* I would appreciate it if you could consider this problem as an extra problem, and if possible, I would like you to enjoy the other problems first. I would like to challenge those who are willing to crush in this contest.

D Sorry for the slow query for the problem. But we weren't just neglecting. We made an effort in our own way. I have asked such a question so that you can enjoy the scale of that effort.

Problem: D Write a program that handles the server side of the problem.

Since the goal of this problem is to create a program that really meets the requirements of the D problem, we do not consider the orientation / unsuitability of each language. Those who have achieved the fastest execution speed may be adopted as a judge program when it is recorded in AOJ, so please try it.

Input format

The input is given in the following format.


N
p_1 ... p_N
Q
l_1 r_1
...
l_Q r_Q


The first row gives the length N of the permutation p. In the second line, N integers representing the permutation p are given, separated by blanks. The third line gives an integer Q that represents the number of queries. The i-th line of the following Q line consists of two integers l_i and r_i separated by blanks, indicating that the query asks for the degree of complexity of the interval [l_i, r_i].

The input satisfies the following constraints.

* 1 \ ≤ N \ ≤ 100,000
* 1 \ ≤ p_i \ ≤ N, p_i \ neq p_j (i \ neq j)
* 1 \ ≤ Q \ ≤ 200,000
* 1 \ ≤ l_i \ ≤ r_i \ ≤ N



Output format

For each Q query i, output the degree of complexity of the interval [l_i, r_i] of p to the i-line. However, the complex degree of the interval [l_i, r_i] of p is (the number of elements of \\ {(i, j) | p_i> p_j {\ rm for} l \ ≤ i <j \ ≤ r \\}). Is defined as.

Input example 1


Four
4 1 3 2
2
13
twenty four


Output example 1


2
1


Input example 2


1
1
1
1 1


Output example 2


0





Example

Input

4
4 1 3 2
2
1 3
2 4


Output

2
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are N robots numbered 1 to N placed on a number line. Robot i is placed at coordinate X_i. When activated, it will travel the distance of D_i in the positive direction, and then it will be removed from the number line. All the robots move at the same speed, and their sizes are ignorable.
Takahashi, who is a mischievous boy, can do the following operation any number of times (possibly zero) as long as there is a robot remaining on the number line.
 - Choose a robot and activate it. This operation cannot be done when there is a robot moving.
While Robot i is moving, if it touches another robot j that is remaining in the range [X_i, X_i + D_i) on the number line, Robot j also gets activated and starts moving. This process is repeated recursively.
How many possible sets of robots remaining on the number line are there after Takahashi does the operation some number of times? Compute this count modulo 998244353, since it can be enormous.

-----Constraints-----
 - 1 \leq N \leq 2 \times 10^5
 - -10^9 \leq X_i \leq 10^9
 - 1 \leq D_i \leq 10^9
 - X_i \neq X_j (i \neq j)
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N
X_1 D_1
:
X_N D_N

-----Output-----
Print the number of possible sets of robots remaining on the number line, modulo 998244353.

-----Sample Input-----
2
1 5
3 3

-----Sample Output-----
3

There are three possible sets of robots remaining on the number line: \{1, 2\}, \{1\}, and \{\}.
These can be achieved as follows:
 - If Takahashi activates nothing, the robots \{1, 2\} will remain.
 - If Takahashi activates Robot 1, it will activate Robot 2 while moving, after which there will be no robots on the number line. This state can also be reached by activating Robot 2 and then Robot 1.
 - If Takahashi activates Robot 2 and finishes doing the operation, the robot \{1\} will remain.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are two popular keyboard layouts in Berland, they differ only in letters positions. All the other keys are the same. In Berland they use alphabet with 26 letters which coincides with English alphabet.

You are given two strings consisting of 26 distinct letters each: all keys of the first and the second layouts in the same order. 

You are also given some text consisting of small and capital English letters and digits. It is known that it was typed in the first layout, but the writer intended to type it in the second layout. Print the text if the same keys were pressed in the second layout.

Since all keys but letters are the same in both layouts, the capitalization of the letters should remain the same, as well as all other characters.

Input

The first line contains a string of length 26 consisting of distinct lowercase English letters. This is the first layout.

The second line contains a string of length 26 consisting of distinct lowercase English letters. This is the second layout.

The third line contains a non-empty string s consisting of lowercase and uppercase English letters and digits. This is the text typed in the first layout. The length of s does not exceed 1000.

Output

Print the text if the same keys were pressed in the second layout.

Examples

Input

qwertyuiopasdfghjklzxcvbnm
veamhjsgqocnrbfxdtwkylupzi
TwccpQZAvb2017


Output

HelloVKCup2017


Input

mnbvcxzlkjhgfdsapoiuytrewq
asdfghjklqwertyuiopzxcvbnm
7abaCABAABAcaba7


Output

7uduGUDUUDUgudu7

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The only difference between easy and hard versions is the length of the string. You can hack this problem only if you solve both problems.

Kirk has a binary string $s$ (a string which consists of zeroes and ones) of length $n$ and he is asking you to find a binary string $t$ of the same length which satisfies the following conditions:



 For any $l$ and $r$ ($1 \leq l \leq r \leq n$) the length of the longest non-decreasing subsequence of the substring $s_{l}s_{l+1} \ldots s_{r}$ is equal to the length of the longest non-decreasing subsequence of the substring $t_{l}t_{l+1} \ldots t_{r}$;

 The number of zeroes in $t$ is the maximum possible.

A non-decreasing subsequence of a string $p$ is a sequence of indices $i_1, i_2, \ldots, i_k$ such that $i_1 < i_2 < \ldots < i_k$ and $p_{i_1} \leq p_{i_2} \leq \ldots \leq p_{i_k}$. The length of the subsequence is $k$.

If there are multiple substrings which satisfy the conditions, output any.


-----Input-----

The first line contains a binary string of length not more than $2\: 000$.


-----Output-----

Output a binary string which satisfied the above conditions. If there are many such strings, output any of them.


-----Examples-----
Input
110

Output
010

Input
010

Output
010

Input
0001111

Output
0000000

Input
0111001100111011101000

Output
0011001100001011101000



-----Note-----

In the first example: 

 For the substrings of the length $1$ the length of the longest non-decreasing subsequnce is $1$;  For $l = 1, r = 2$ the longest non-decreasing subsequnce of the substring $s_{1}s_{2}$ is $11$ and the longest non-decreasing subsequnce of the substring $t_{1}t_{2}$ is $01$;  For $l = 1, r = 3$ the longest non-decreasing subsequnce of the substring $s_{1}s_{3}$ is $11$ and the longest non-decreasing subsequnce of the substring $t_{1}t_{3}$ is $00$;  For $l = 2, r = 3$ the longest non-decreasing subsequnce of the substring $s_{2}s_{3}$ is $1$ and the longest non-decreasing subsequnce of the substring $t_{2}t_{3}$ is $1$; 

The second example is similar to the first one.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Vitya and Strange Lesson

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Today at the lesson Vitya learned a very interesting function — mex. Mex of a sequence of numbers is the minimum non-negative number that is not present in the sequence as element. For example, *mex*([4,<=33,<=0,<=1,<=1,<=5])<==<=2 and *mex*([1,<=2,<=3])<==<=0.

Vitya quickly understood all tasks of the teacher, but can you do the same?

You are given an array consisting of *n* non-negative integers, and *m* queries. Each query is characterized by one number *x* and consists of the following consecutive steps:
 -  Perform the bitwise addition operation modulo 2 (xor) of each array element with the number *x*. -  Find mex of the resulting array. 
Note that after each query the array changes.

Input Specification:
First line contains two integer numbers *n* and *m* (1<=≤<=*n*,<=*m*<=≤<=3·105) — number of elements in array and number of queries.

Next line contains *n* integer numbers *a**i* (0<=≤<=*a**i*<=≤<=3·105) — elements of then array.

Each of next *m* lines contains query — one integer number *x* (0<=≤<=*x*<=≤<=3·105).

Output Specification:
For each query print the answer on a separate line.

Demo Input:
['2 2\n1 3\n1\n3\n', '4 3\n0 1 5 6\n1\n2\n4\n', '5 4\n0 1 5 6 7\n1\n1\n4\n5\n']

Demo Output:
['1\n0\n', '2\n0\n0\n', '2\n2\n0\n2\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a three-digit positive integer N.

Determine whether N is a palindromic number.

Here, a palindromic number is an integer that reads the same backward as forward in decimal notation.

-----Constraints-----
 - 100≤N≤999
 - N is an integer.

-----Input-----
Input is given from Standard Input in the following format:  
N

-----Output-----
If N is a palindromic number, print Yes; otherwise, print No.

-----Sample Input-----
575

-----Sample Output-----
Yes

N=575 is also 575 when read backward, so it is a palindromic number. You should print Yes.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Your users passwords were all stole in the Yahoo! hack, and it turns out they have been lax in creating secure passwords.  Create a function that checks their new password (passed as a string) to make sure it meets the following requirements:


Between 8 - 20 characters

Contains only the following characters: (and at least one character from each category): uppercase letters, lowercase letters, digits, and the special characters !@#$%^&*?




Return "valid" if passed or else "not valid"

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