Description

Define the level 1 string s1 = “OuQ”,
and the level k string sk = “O” + sk−1 + “u” + sk−1 + “Q”.

For example:

• s2 = “O” + s1 + “u” + s1 + “Q” = “OOuQuOuQQ”
• s3 = “OOOuQuOuQQuOOuQuOuQQQ”

Given 3 integeres k,l,r.
Please find all characters of sk[l],sk[l+1],...sk[r−1],sk[r]

Input

There’re multiple testcases in input.
Three integers k,l,r on each line.

• 1 ≤ k ≤ 50
• 0 ≤ l ≤ r < length of sk
• 1 ≤ |r−l+1| ≤ 100

Output

For each testcase, print |r−l+1| characters,sk[l],sk[l+1],...sk[r−1],sk[r], for a line.

Remember ‘\n’ on the end of each line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

There will be a launch of a new, powerful and unusual collider very soon, which located along a straight line. n particles will be launched inside it. All of them are located in a straight line and there can not be two or more particles located in the same point. The coordinates of the particles coincide with the distance in meters from the center of the collider, xi is the coordinate of the i-th particle and its position in the collider at the same time. All coordinates of particle positions are even integers.

You know the direction of each particle movement — it will move to the right or to the left after the collider’s launch start. All particles begin to move simultaneously at the time of the collider’s launch start. Each particle will move straight to the left or straight to the right with the constant speed of 1 meter per microsecond. The collider is big enough so particles can not leave it in the foreseeable time.

Write the program which finds the moment of the first collision of any two particles of the collider. In other words, find the number of microseconds before the first moment when any two particles are at the same point.

This Problem is reproduced from http://codeforces.com/problemset/problem/699/A

Input

The first line contains the positive integer n (1  ≤ n  ≤ 200 000) — the number of particles.

The second line contains n symbols “L” and “R”. If the i-th symbol equals “L”, then the i-th particle will move to the left, otherwise the i-th symbol equals “R” and the i-th particle will move to the right.

The third line contains the sequence of pairwise distinct even integers x1,x2,...,xn (0 ≤ xi ≤ 10⁹) — the coordinates of particles in the order from the left to the right. It is guaranteed that the coordinates of particles are given in the increasing order.

Output

In the first line print the only integer — the first moment (in microseconds) when two particles are at the same point and there will be an explosion.

Print the only integer −1, if the collision of particles doesn’t happen.

Remember ‘\n’ on the end of each line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The name of one small but proud corporation consists of n lowercase English letters. The Corporation has decided to try rebranding — an active marketing strategy, that includes a set of measures to change either the brand (both for the company and the goods it produces) or its components: the name, the logo, the slogan. They decided to start with the name.

For this purpose the corporation has consecutively hired m designers. Once a company hires the i-th designer, he immediately contributes to the creation of a new corporation name as follows: he takes the newest version of the name and replaces all the letters xi by yi, and all the letters yi by xi. This results in the new version. It is possible that some of these letters do no occur in the string. It may also happen that xi coincides with yi. The version of the name received after the work of the last designer becomes the new name of the corporation.

Manager Arkady has recently got a job in this company, but is already soaked in the spirit of teamwork and is very worried about the success of the rebranding. Naturally, he can’t wait to find out what is the new name the Corporation will receive.

Satisfy Arkady’s curiosity and tell him the final version of the name.

This Problem is reproduced from http://codeforces.com/problemset/problem/591/B

Input

The first line of the input contains two integers n and mm (1 ≤ n, m ≤ 200,000)— the length of the initial name and the number of designers hired, respectively.

The second line consists of nn lowercase English letters and represents the original name of the corporation.

Next m lines contain the descriptions of the designers’ actions: the i-th of them contains two space-separated lowercase English letters xi and yi.

Output

Print the new name of the corporation.

Sample Input  Download

Sample Output  Download

Tags

Discuss