You are given a list of integers x_1,x_2,\ldots,x_nx1​,x2​,…,xn​ and a number kk. It is guaranteed that each i from 1 to k appears in thelist at least once.Find the lexicographically smallest subsequence of x that contains each integer from 1 to k exactly once.

input

The first line will contain two integers nn and kk, with 1 \leq k \leq n \leq 200 0001≤k≤n≤200000. The following n lines will each containan integer x_ixi​ with 1 \leq x_i \leq k1≤xi​≤k.

output

Write out on one line, separated by spaces, the lexicographically smallest subsequence of x that has each integer from 1 to k exactly once

Alice and Bob are playing a game on a simple connected graph with N nodes and M edges.Alice colors each edge in the graph red or blue.A path is a sequence of edges where each pair of consecutive edges have a node in common. If the first edge in thepair is of a different color than the second edge, then that is a “color change.”After Alice colors the graph, Bob chooses a path that begins at node 1 and ends at node N. He can choose any path onthe graph, but he wants to minimize the number of color changes in the path. Alice wants to choose an edge coloringto maximize the number of color changes Bob must make. What is the maximum number of color changes she canforce Bob to make, regardless of which path he chooses?

Input

The first line contains two integer values N and M with 2 \leq N \leq 100 0002≤N≤100000 and 1 \leq M \leq 100 0001≤M≤100000. The next M linescontain two integers a_iai​ and b_ibi​ indicating an undirected edge between nodes a_iai​ and b_ibi​ (1 \leq a_i,b_i \leq N1≤ai​,bi​≤N, a_i \neq b_iai​​=bi​).All edges in the graph are unique.

Output

Output the maximum number of color changes Alice can force Bob to make on his route from node 1 to node N

You are given two integers, A and B. You want to transform A to B by performing a sequence of operations. You canonly perform the following operations:

• Divide A by two, but only if A is even
• Add one to A.

What is the minimum number of operations you need to transform A into B?

input

The input will be a single line containing two integers A and B with 1 \leq A,B \leq 10^91≤A,B≤109.

output

On a single line write the minimum number of operations required as an integer.

Define a string to be a rainbow string if every letter in the string is distinct. An empty string is also considered a rainbow string.

Given a string of lowercase letters, compute the number of different subsequences which are rainbow strings. Two subsequences are different if an index is included in one subsequence but not the other, even if the resulting strings areidentical.

In the first example, there are 8 subsequences. The only subsequences that aren't rainbow strings are aaaa and aabaab.The remaining 6 subsequences are rainbow strings.

input

The input will consist of a single line with a single string consisting solely of lowercase letters. The length of the stringis between 1 and 100 000 (inclusive).

output

Write on a single line the number of rainbow sequences, modulo the prime 11092019.

Charles and Ada are watching a magician shuffling a deck of thirteen numbered cards, which were originally ordered.The magician spreads the cards out on the table.

Ada exclaims, “Odd; ten of the cards are in their original locations!”

Charles thinks for a moment, and says, “Not only that, but it is the forty-second such ordering!”

Can you figure out the order of the cards? Formally, the magician’s cards can be considered as a permutationp_1, p_2, ..., p_np1​,p2​,...,pn​, that contains each number from 1 to nn exactlyexactly once. The number of fixed points is the number ofindices ii such that p_i = ipi​=i.

Given three numbers n, mn,m and kk, find the kkth lexicographically smallest permutation of sizesize nn that has exactly m fixed points.

Input

The input will be a single line containing the three integers n, mn,m, and kk, with 0 ≤ m ≤ n0≤m≤n, 1 ≤ n ≤ 501≤n≤50, and 1 ≤ k ≤ 10^{18}1≤k≤1018.

Output

On a single line, write the permutation as a sequence of nn space-separated integers. If there are fewer than kk permutation satisfying the conditions, then print -1 on a single line.

An LCD panel is composed of a grid of pixels, spaced 11 alu (“arbitrary length unit”) apart both horizontally andvertically. Wires run along each row and each column, intersecting at the pixels. Wires are numbered beginning with 11 and proceeding up to a panel-dependent maximum. The vertical wire numbered 11 lies along the left edge of the panel,and the horizontal wire numbered 11 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 speedof 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 wirereaches 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 will contain nn, the number of current pulses, with 1 ≤ n ≤ 200 0001≤n≤200000.Following this will be nn lines, each describing a single pulse. Each such line will contain 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 ≤ t ≤ 200 0001≤t≤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 ≤ m ≤ 200 0001≤m≤200000, denoting the length of the pulse.
• An integer aa, 1 ≤ a ≤ 100 0001≤a≤100000, denoting the wire number (horizontal or vertical) along which the pulse willtravel.

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.

Consider a set of points PP in the plane such that no 33 points are collinear. We construct a “windmill” as follows:

Choose a point pp in PP and a starting direction such that the line through pp in that direction does not intersect any otherpoints in PP.Draw that line.

Slowly rotate the line clockwise like a windmill about the point pp as its pivot until the line intersects another point p'p′ in PP. Designate that point p'p′ to be the new pivot (call this “promoting” the point p'p′), and then continue the rotation.

Continue this process until the line has rotated a full 360360 degrees, returning to its original direction (it can be shown that the line will also return to its original position after a 360360 degree rotation).

During this process, a given point can be promoted multiple times. Considering all possible starting pivots and orientations, find the maximum number of times that a single point can be promoted during a single 360360 degree rotation of a line.

Input

The first line of the input will be a single integer nn with 2 ≤ n ≤ 20002≤n≤2000. Following this will be nn lines, each with two integers x_ixi​ and y_iyi​ with -10 000 ≤ xi,yi ≤ 10 000−10000≤xi,yi≤10000.

Output

On one line, write an integer with the largest number of times any particular point can be a pivot when an arbitrarystarting line does a full rotation as described above.

You are given WW, a set of NN words that are anagrams of each other. There are no duplicate letters in any word. A setof words S \subseteq WS⊆W is called “swap-free” if there is no way to turn a word x \in Sx∈S into another word y \in Sy∈S by swappingonly a single pair of (not necessarily adjacent) letters in xx. Find the size of the largest swap-free set SS chosen from thegiven set WW.

Input

The first line of input contains an integer NN (1 ≤ N ≤ 5001≤N≤500). Following that are NN lines each with a single word.Every word contains only lowercase English letters and no duplicate letters. All NN words are unique, have at least oneletter, and every word is an anagram of every other word.

Output

Output the size of the largest swap-free set

You are planning to travel in interstellar space in the hope of finding habitable planets. You have already identified NN stars that can recharge your spaceship via its solar panels. The only work left is to decide the orientation of thespaceship that maximizes the distance it can travel.

Space is modeled as a 2D2D plane, with the Earth at the origin. The spaceship can be launched from the Earth in a straight line, in any direction. Star ii can provide enough energy to travel T_iTi​ distance if the spaceship is launched at an angle of a_iai​ with the xx-axis. If the angle is not perfectly aligned, then the spaceship gets less energy. Specifically, if the launch direction makes an angle of aa with the xx-axis, then it gets enough energy to travel distance of

max(0, T_i-s_i * dist(a_i,a))max(0,Ti​−si​∗dist(ai​,a))

from star ii, where dist(a, b)dist(a,b) is the minimum radians needed to go from angle aa to bb. The distance that the spaceship can travel is simply the sum of the distances that each star contributes. Find the maximum distance TT that the star ship can travel.

Input

The first line contains the value NN, 1 ≤ N ≤ 10^51≤N≤105. Following this are NN lines each containing three real numbers T_iTi​,s_isi​, and a_iai​, with 0 < T_i ≤ 1 0000<Ti​≤1000, 0 ≤ si ≤ 1000≤si≤100, and 0 ≤ a_i < 2\pi0≤ai​<2π. All real numbers in the input have at most 66 digits after the decimal point.

Output

On a single line output the maximum distance the spacecraft can travel. Your answer is considered correct if it has anabsolute or relative error of at most 10^{−6}10−6.

Your computer has a cache consisting of nn different addresses, indexed from 11 to nn. Each address can contain a singlebyte. The i^{th}ith byte is denoted as a_iai​. Initially all cache bytes start off with the value zero. Formally, the cache can bemodeled by a byte array of length nn that is initially all zeros.

You have mm different pieces of data you want to store. The i^{th}ith piece of data is a byte array x_ixi​ of length s_isi​.You are going to do qq different operations on your computer. There are three types of operations:

11 ii pp

Load data ii starting at position pp in the cache. Formally, this means set a_p = x_{i,1}, a_{p+1} = x_{i,2},...,a_{p+s_i-1} =x_{i,s_i}ap​=xi,1​,ap+1​=xi,2​,...,ap+si​−1​=xi,si​​, where x_{i,k}xi,k​ represents the kkth byte of the array x_ixi​. This overwrites any previously stored value in thecache. It is guaranteed that this is a valid operation (e.g. s_i + p - 1 ≤ nsi​+p−1≤n). It is possible for multiple versions of some data to be loaded in multiple positions at once.

22 pp

Print the byte that is stored in address pp.

33 ii ll rr

Increment the l^{th}lth through r^{th}rth bytes in the i^{th}ith piece of data, modulo 256. Formally, this means to set x_{i,k} =(x_{i,k} + 1)xi,k​=(xi,k​+1) mod 256256 for l ≤ k ≤ rl≤k≤r. This does not affect values that are already loaded in the cache and only affects future loads.

Input

The first line of input consists of three numbers nn, mm, and qq.The following mm lines consist of descriptions of the data, one per line. The following qq lines consist of descriptions of operations, one per line.It is guaranteed there is at least one type 22 print query operation in the input. Additionally:1\le n,m,q \le 5*10^51≤n,m,q≤5∗105, \Sigma_i s_i \le 5*10^5Σi​si​≤5∗105,s_i \ge 1si​≥1,0 \le x_{i,j} \le 2550≤xi,j​≤255

Output

Your program must output the results for each type 2 operation, one integer value per line.

“Drat!” cursed Charles. “This stupid carry bar is not working in my Engine! I just tried to calculate the square of anumber, but it’s wrong; all of the carries are lost.”

“Hmm,” mused Ada, “arithmetic without carries! I wonder if I can figure out what your original input was, based onthe result I see on the Engine.”

CarrylessCarryless additionaddition, denoted by \oplus⊕, is the same as normal addition, except any carries are ignored (in base 1010). Thus,37 \oplus 4837⊕48 is 7575, not 8585.

CarrylessCarryless multiplicationmultiplication, denoted by \otimes⊗, is performed using the schoolboy algorithm for multiplication, column bycolumn, but the intermediate additions are calculated using carrylesscarryless additionaddition. More formally, Let a_ma_{m-1}...a_1a_0am​am−1​...a1​a0​be the digits of aa, where a_0a0​ is its least significant digit. Similarly define b_nb_{n-1}...b_{1}b_0bn​bn−1​...b1​b0​ be the digits of bb. The digitsof c = a \otimes bc=a⊗b are given by the following equation:

c_k=a_0b_k \oplus a_1b_{k-1}\oplus ... \oplus a_{k-1}b_1 \oplus a_kb_0,ck​=a0​bk​⊕a1​bk−1​⊕...⊕ak−1​b1​⊕ak​b0​,

where any a_iai​ or b_jbj​ is considered zero if i > mi>m or j > nj>n. For example, 9 \otimes 1 2349⊗1234 is 9 8769876, 90 \otimes 1 23490⊗1234 is 98 76098760, and 99 \otimes 1 23499⊗1234 is 97 53697536.Given NN, find the smallest positive integer a such that a \otimes a = Na⊗a=N.

Input

The input consists of a single line with an integer NN, with at most 2525 digits and no leading zeros.

Output

Print, on a single line, the least positive number aa such that a \otimes a = Na⊗a=N. If there is no such a, print ‘-1−1’ instead.

Given an orthogonal maze rotated 4545 degrees and drawn with forward and backward slash characters (see below),determine the minimum number of walls that need to be removed to ensure it is possible to escape outside of the mazefrom every square of the (possibly disconnected) maze.

/\

\/

This maze has only a single square fully enclosed. Removing any wall will connect it to the outside.

/\..

\.\.

.\/\

..\/

This maze has two enclosed areas. Two walls need to be removed to connect all squares to the outside.

Input

The first line has two numbers, RR and CC, giving the number of rows and columns in the maze's input description.Following this will be RR lines each with CC characters, consisting only of the characters ‘/’, ‘\’, and ‘..’. Both RR and CC are in the range 1...1 0001...1000.Define an odd (even) square as one where the sum of the xx and yy coordinates is odd (even). Either all forward slasheswill be in the odd squares and all backslashes in the even squares, or vice versa.

Output

Output on a single line an integer indicating how many walls need to be removed so escape is possible from everysquare in the maze.