BSUIR Open XII: Student Final
A. The Generalized Cannonball Problem
time limit per test
8 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The cannonball problem is to find such a number of cannonballs that they can be stacked in a single layer in the form of a square and in the form of a pyramid with a square base. It is easy to see that such a problem can be reduced to finding natural $$$n$$$ and $$$m$$$ such that:

$$$$$$\sum_{i=1}^{n}i^2 = m^2$$$$$$

It is known for sure that there are exactly two solutions: $$$n = 1$$$ and $$$m = 1$$$, that is, one cannonball, and $$$n = 24$$$ and $$$m = 70$$$, that is, $$$70^2 = 4900$$$ cannonballs.

In the era of interstellar travel, this arrangement may not be entirely convenient. For example, pirate spaceships use cannonballs arranged in the shape of a truncated pyramid consisting of exactly $$$k$$$ layers. This way we get a generalized cannonball problem, which can be reduced to finding, for a given $$$k$$$, natural numbers $$$n$$$ and $$$m$$$ such that:

$$$$$$\sum_{i=1}^{k}(n+i-1)^2 = m^2$$$$$$

To effectively combat space piracy, it was decided to study this problem. You are asked to find any solution to a problem for a given $$$k$$$. Since $$$m$$$ is uniquely determined from $$$n$$$, you are asked to find only $$$n$$$.

Figure 1. An example of stacking cannonballs in the shape of a truncated pyramid ($$$n = 3$$$, $$$k = 3$$$)
Input

The first line contains a single integer $$$t$$$ — the number of values of $$$k$$$ for which the authors want to find out the solution.

In the following $$$t$$$ lines, a single integer $$$k$$$ — is specified, a value for which at least one solution must be found.

$$$$$$1 \le t \le 10$$$$$$ $$$$$$1 \le k \le 2500 $$$$$$

Output

For each given $$$k$$$, print "Yes" on a separate line if there is a solution, otherwise print "No". If there is a solution, then in the next line print a single positive integer $$$n$$$ — any solution to the generalized cannonball problem that does not exceed $$$10^{18}$$$.

It is guaranteed that if a solution exists, then there is a solution not exceeding $$$10^{18}$$$.

Examples
Input
3
4
6
24
Output
No
No
Yes
1
Input
1
529
Output
Yes
255

B. Reliable delivery
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A fairly successful entrepreneur decided to establish deliveries of his products to a star system with two inhabited planets. For this purpose, a teleportation chamber was installed on each planet. A similar chamber was also located on the enterprise's premises. The enterprise's chamber is capable of teleporting exactly one container of products to one of the planets in one unit of time. A switch is used to select to which planet the goods should be teleported.

The enterprise produces a total of $$$m$$$ types of products. You have been provided with a schedule of goods delivery, which consists of $$$n$$$ non-intersecting time intervals. During the $$$i$$$-th time interval, containers of a certain type of goods $$$t_i$$$ will be loaded into the teleportation chamber from the $$$l_i$$$-th unit of time to the $$$r_i$$$-th unit of time, inclusive. Since teleportation takes exactly one unit of time, exactly $$$r_i-l_i+1$$$ containers will be loaded during the $$$i$$$-th interval. Due to production peculiarities, the schedule cannot contain more than two time intervals with the delivery of containers of the same type of product.

Your task is to ensure that an equal number of containers of each type of product is delivered to each planet. Since frequent use of the switch can break the teleportation chamber, you are asked to make no more than $$$m$$$ switches.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ — the number of time intervals in the delivery schedule and the number of types of products, respectively.

The next $$$n$$$ lines contain three integers each: $$$t_i$$$, $$$l_i$$$, and $$$r_i$$$ — the type of product in the $$$i$$$-th time interval, as well as the start and end of the $$$i$$$-th time interval, respectively.

$$$$$$1 \le m \le n \le 10^5$$$$$$ $$$$$$1 \le t_i \le m$$$$$$ $$$$$$1 \le l_i \le r_i \le 10^9$$$$$$ $$$$$$r_i \lt l_{i+1}$$$$$$

Output

In the first line, print "Yes" if it is possible to deliver an equal number of containers of each type of product using no more than $$$m$$$ switches.

If delivery is not possible, then in a single line, print "No".

In the second line, print the number $$$k$$$ ($$$0 \le k \le m$$$) — the number of switches.

In the last line, print $$$k$$$ integers $$$s_i$$$ ($$$1 \le s_i \le 10^9$$$, $$$s_i \lt s_{i+1}$$$) — the times when the switch needs to be used. If there are multiple possible answers, you can output any.

Note that the switch at time $$$x$$$ always occurs before the teleportation of goods at time $$$x$$$.

Examples
Input
4 3
1 1 2
2 3 6
3 8 9
1 11 14
Output
Yes
3
5 9 12
Input
1 1
1 1 3
Output
No
Input
5 3
1 1 2
2 3 4
3 5 8
2 9 10
1 11 12
Output
Yes
1
7

C. Cake and Candles
time limit per test
2 s
memory limit per test
256 megabytes
input
standard input
output
standard output

There is a cake with a radius of $$$r$$$, the center of which is located at $$$(0, 0)$$$. There are also $$$n$$$ candles, where the $$$i$$$-th candle has coordinates $$$(x_i, y_i)$$$ and is strictly inside the cake. Vadim wants to blow out all these candles at once, as only then his secret dream will come true.

Vadim can stand at any point on the plane (denoted by the letter $$$V$$$ in the figure below) and look in any direction. In this case, he will be able to blow out all the candles that belong to a certain angle with the vertex at $$$V$$$ and a magnitude of $$$\theta$$$.

  Figure 1. Candles blown out are shown in gray, not blown out in orange. Vadim and the direction (angle) in which he blows out the candles are shown in purple. Here, $$$\theta = 42^{\circ}$$$.

Vadim does not want to stay far from the cake, as immediately after blowing out all the candles, he will start eating it. Therefore, he asks for your help to calculate the minimum distance he needs to move away from the cake in order to blow out all the candles (the distance is measured from the center of the cake).

Please note that the cake will be eaten afterwards, so Vadim should not climb on it (in other words, the answer should always be greater than or equal to $$$r$$$).

Input

The first line specifies $$$t$$$ — the number of test cases.

The first line of each test case specifies the natural numbers $$$n$$$, $$$r$$$, $$$\theta$$$ — the number of candles, the radius of the cake, and the angle that Vadim can blow out.

The following $$$n$$$ lines specify pairs of integers $$$x_i$$$, $$$y_i$$$ — the coordinates of the $$$i$$$-th candle.

$$$$$$1 \le t \le 20\,000$$$$$$ $$$$$$1 \le \sum n \le 200\,000$$$$$$ $$$$$$1 \le r \le 10^9$$$$$$ $$$$$$20 \le \theta \le 120$$$$$$ $$$$$$x_i^2 + y_i^2 \le r^2$$$$$$

Output

For each test case, output the minimum distance Vadim needs to move away. The answer is correct if the absolute or relative error does not exceed $$$10^{-9}$$$.

Examples
Input
1
5 2 30
0 0
-1 -1
1 1
-1 1
1 -1
Output
4.574735318057
Input
2
2 2 90
1 0
-1 0
1 2 20
1 1
Output
2.000000000000
2.000000000000

D. Difficult problem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In order to visit the center of the galaxy and see a quasar from a close distance, it is necessary to go through a fairly long and dangerous path. During the journey to the center of the galaxy, you encounter a space patrol. You are warned that in order to continue moving, you need to provide the password — a positive integer $$$x$$$, otherwise you will be destroyed. You have the opportunity to ask no more than $$$32$$$ questions of the following type: how many prime numbers $$$p$$$ exist such that there is an integer $$$i$$$ such that $$$p \cdot i = \lfloor \frac{n}{q} \rfloor$$$, where $$$q$$$ is the number you ask in the question. In response, you will receive the number of such prime numbers, or $$$-1$$$ if there are infinitely many.

Interaction

To ask a question, you need to output the string: "? q", where $$$q$$$ is some positive integer. In response, you will receive a single number — the number of prime numbers satisfying the condition of your request.

Once you have determined the password, output in a separate line "! x". After that, your program should immediately terminate.

$$$$$$1 \le x, q \le 10^9$$$$$$

If your program asks more than $$$32$$$ questions, it will receive the verdict "Wrong Answer".

Examples
Input
? 4

? 8

! 8
Output

1

0
Input
? 4

? 8

? 21

! 42
Output

2

1

1

E. Safe Memory Management
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You have probably heard of the Rust programming language. Perhaps you even know that it guarantees safe memory management thanks to its built-in system of static reference checking. Recently, this language has become widely popular across the visible universe.

During a journey to a star system where a fashion exhibition will take place, the Lorenzo spaceship experienced a malfunction. Due to incorrect warp jump parameter settings, the ship ended up in a quantum turbulence and found itself in the pirate system PRS-1. Unfortunately, the ship was captured by the pirates, and during the negotiations, Lorenzo heard the phrase "Please, use Rust. Use it blazingly fast" several times.

As it turned out, the pirates were obsessed with this language. Furthermore, they were only interested in safe memory management, which involved only memory allocation and deallocation operations. The pirates had absolutely no interest in other features of this remarkable language.

For memory allocation, the pirates use the following construction:

let X = new();

Here and below, "X" denotes the name of a variable consisting only of lowercase Latin letters.

For explicit memory deallocation, the pirates use the following construction:

drop(X);

The language automatically deallocates memory when a variable goes out of scope. To specify the beginning and end of the scope, the symbols "{" and "}" are used, respectively:

{
  let X = new();
}

In case of going out of scope, the compiler adds memory deallocation constructions for variables not yet deallocated in this scope in reverse declaration order, for example:

{
  let a = new();
  let b = new();
  let c = new();
  let d = new();
  drop(c);
}

Will be transformed by the compiler into:

let a = new();
let b = new();
let c = new();
let d = new();
drop(c);
drop(d); // <-
drop(b); // <-
drop(a); // <-

As ransom for the ship, the pirates offered Lorenzo to improve the provided Rust code. Since the pirates only use explicit memory management and do not use automatic deallocation (scopes), they ask you to rewrite their code in a way that minimizes the number of explicit memory deallocation constructions, while not changing the order of memory allocation and deallocation.

Lorenzo still has a chance to make it to the exhibition, but he has absolutely no knowledge of programming, so he asks you to solve this problem.

Input

The first line contains a single integer $$$n$$$ — the number of lines in the pirates' code.

The next $$$n$$$ lines contain the pirates' code. Each line has one of two formats:

  • "let X = new();" — memory allocation for a variable named 'X'.
  • "drop(X);" — memory deallocation for a variable named 'X'.

It is guaranteed that all created variables have unique names consisting only of lowercase Latin letters, with a length not exceeding $$$16$$$ characters. It is also guaranteed that each memory allocation is followed by a single memory deallocation (memory allocation always precedes deallocation).

$$$$$$2 \le n \le 1000$$$$$$

Output

Output the transformed pirates' code containing the minimum number of explicit memory deallocation constructions. If there are multiple possible answers, any one containing the minimum number of scopes is allowed. Consider the entire code to already be within a certain scope.

Each line should have one of the four formats:

  • "let X = new();" — memory allocation for a variable named 'X'.
  • "drop(X);" — memory deallocation for a variable named 'X'.
  • "{" — start of a scope.
  • "}" — end of a scope.

You may also add any number of spaces at the beginning of each line (but not exceeding $$$4\,000$$$).

Examples
Input
6
let aba = new();
let caba = new();
let daba = new();
drop(aba);
drop(daba);
drop(caba);
Output
let aba = new();
let caba = new();
let daba = new();
drop(aba);
Input
8
let a = new();
let b = new();
drop(b);
let c = new();
drop(c);
drop(a);
let e = new();
drop(e);
Output
{
  let a = new();
  {
    let b = new();
  }
  let c = new();
}
let e = new();

F. Wormholes
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

As is well known, Alexander loves to travel through space. The space itself is a field of size $$$n$$$ by $$$m$$$ cells. Each cell can be of one of two types: the first type is the most common space cell, and the second type is a wormhole, which instantly moves from this cell to a neighboring one (up, right, down, and left). At the moment, Alexander wants to fly on his ship from cell $$$(1, 1)$$$ to cell $$$(n, m)$$$.

In one hour, he can fly to a neighboring cell (up, right, down, and left), and he can also remove a wormhole in any cell at any time. After this, the cell with the wormhole will become a regular space cell, but this procedure is very expensive, and Alexander does not want to waste resources unnecessarily, so he wants to remove the minimum number of such cells. Movement in wormholes is instantaneous, therefore it does not take time.

Also, if a wormhole leads beyond the space field, the spaceship will crash, which Alexander definitely does not want.

Help Alexander spend the minimum amount of money and reach cell $$$(n, m)$$$ in the minimum number of hours from cell $$$(1, 1)$$$.

Input

The first line contains two numbers $$$n$$$ and $$$m$$$ — the sizes of the space.

Then there are $$$n$$$ lines, each containing $$$m$$$ characters.

Each character is one of the following:

  • "." — if this cell is a regular space cell.
  • "U" — if this cell has a wormhole that moves the ship from this cell to the cell above it.
  • "R" — if this cell has a wormhole that moves the ship from this cell to the cell to the right of it.
  • "D" — if this cell has a wormhole that moves the ship from this cell to the cell below it.
  • "L" — if this cell has a wormhole that moves the ship from this cell to the cell to the left of it.

Cells $$$(1, 1)$$$ and $$$(n, m)$$$ will always be regular space cells.

$$$$$$1 \le n \le 10^5$$$$$$ $$$$$$1 \le m \le 10^5$$$$$$ $$$$$$1 \le n \cdot m \le 10^6$$$$$$

Output

Output two numbers, the first being the minimum number of removed wormholes, and the second number being the number of hours spent on the path when removing the minimum number of wormholes.

Examples
Input
1 4
.RR.
Output
0 1
Input
2 3
.D.
.D.
Output
1 2
Input
5 5
.U...
.U.D.
.U.D.
.U.D.
...D.
Output
0 16

G. Slot Machines
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Due to the rapid development of humanity in the space sphere, the fairy tales that parents tell their children have become distorted. They have ceased to be interesting or funny and have turned into computer science problems. For example, Martian children are told the following problem at night.

Once upon a time, there were three friends — Sasha, Kirill, and Yuri. At some point, they ran out of money. Therefore, they decided to build a casino and started to come up with rules:

  • Sasha: — There will be $$$a$$$ stones in the slot machine, and you can take any number of stones from $$$1$$$ to $$$k$$$ in one move;
  • Kirill: — If someone takes the same number of stones from the machine as the previous person, they lose.
  • Yuri: — There will be $$$n$$$ slot machines, and the $$$i$$$-th one will contain $$$a_i$$$ stones.

Playing the same game all the time is boring, and there is no element of randomness. Therefore, the friends decided to clarify the rules:

  • Sasha: — When a player enters, a pair of random numbers $$$(l,r)$$$ ($$$1 \le l \le r \le n$$$) is generated for them. In one move, you can take stones from any machine with a number $$$i$$$ such that $$$l \le i \le r$$$.
  • Kirill: — Specially trained staff play with the player, taking turns to make moves, with the player making the first move.
  • Yuri: — The player loses if they cannot make any moves according to the rules of the game, in which case they give their apartment to the casino owners.

The friends also decided to assess the profitability of their scheme, but they couldn't manage it. Therefore, they ask you to help them calculate the number of pairs $$$(l, r)$$$, for which the casino wins the game.

Input

The first line contains the numbers $$$n$$$ and $$$k$$$ — the number of slot machines and the maximum number of stones that can be taken in one move.

The second line contains the numbers $$$a_1, \ldots, a_n$$$ — the initial number of stones in each of the machines.

$$$$$$1 \le n \le 1\,000\,000$$$$$$ $$$$$$2 \le k \le 100$$$$$$ $$$$$$1 \le a_i \le 10^{18}$$$$$$

Output

Output a single number — the answer to the problem.

Examples
Input
3 2
1 2 3
Output
3
Input
2 10
308 693
Output
3
Note

Consider the first example:

  • $$$(l,r)=(1,1)$$$. The player wins, as they can take all the stones in the first move.
  • $$$(l,r)=(2,2)$$$. The player wins, as they can take all the stones in the first move.
  • $$$(l,r)=(3,3)$$$. The casino wins. Let the player take $$$x$$$ stones on the first move, then the casino will take $$$3-x$$$.
  • $$$(l,r)=(1,2)$$$. The casino wins. Note that you can only take stones from a pile of size $$$2$$$ once (if you take only $$$1$$$ stone, you cannot take another one ever, as it would be a repeat move). Therefore, the player will always run out in two moves.
  • $$$(l,r)=(2,3)$$$. The player wins, as in the first move they can take all the stones from the second pile.
  • $$$(l,r)=(1,3)$$$. The casino wins, as they have a strategy for counter moves:
    • If the player takes stones from the first pile, the casino takes stones from the second, and vice versa.
    • If the player takes $$$x$$$ stones from the third pile, the casino takes $$$3-x$$$ stones from the same pile.

Out of all possible pairs $$$(l, r)$$$, $$$3$$$ pairs $$$(3,3)$$$, $$$(1,2)$$$, $$$(1,3)$$$ are suitable for us, so the answer is $$$3$$$.

H. Space Bar
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The annual ICPC (Intergalactic Collegiate Programming Contest) competition is ready to welcome its guests again (this time, fortunately, without any postponements). Among the participants is the well-known team from the Honourable School of Experts, which, according to this year's rules, consists of exactly $$$n$$$ members. The $$$i$$$-th team member evaluates their problem-solving ability at exactly $$$a_i$$$ units.

Deciding not to break the good tradition, the team members decided to visit the equally famous bar "DRYga" on the evening before the start of the main tour. Since the team is quite experienced, they are aware of an interesting pattern that is characteristic of them. Initially, the $$$i$$$-th team member is able to solve exactly $$$0$$$ problems in the competition. After each "special extreme shot" is consumed, the strength of the $$$i$$$-th team member is enhanced by $$$k$$$, allowing him to solve exactly $$$(x + k) \bmod (a_i + 1)$$$ problems in the competition, where $$$x$$$ is the number of problems the member could solve before taking the shot, and $$$a \bmod b$$$ is the operation of taking the remainder of the integer division of $$$a$$$ by $$$b$$$. Throughout the evening, the team only orders "special extreme shots" of strength $$$k$$$, and each team member can order an unlimited number of shots.

Since the team is determined to win the competition this year, they want to order exactly the number of "special extreme shots" of strength $$$k$$$ so that each team member can solve exactly $$$a_i$$$ problems. Help the legendary team calculate the minimum total number of shots they need to order at the bar.

Input

The first line of the input contains two natural numbers $$$n$$$ and $$$k$$$ separated by a space — the number of team members and the strength of the "special extreme shot".

The second line of the input contains $$$n$$$ natural numbers $$$a_1, a_2, a_3, \ldots, a_n$$$ — the problem-solving ability of the $$$i$$$-th team member.

$$$$$$ 1 \le n \le 10^5 $$$$$$ $$$$$$ 1 \le k \le 10^5 $$$$$$ $$$$$$ 0 \le a_i \le 10^5 $$$$$$ $$$$$$ \sum{a_i} \le 10^6 $$$$$$

Output

Output a single number — the minimum number of shots that the team needs to order.

If there is no such quantity of shots for each team member to solve exactly $$$a_i$$$ problems, output $$$-1$$$.

Examples
Input
5 5
1 2 3 5 7
Output
9
Input
5 6
28 16 4 18 20
Output
-1
Note

In the first example, team members with numbers $$$1$$$, $$$2$$$, and $$$4$$$ need to order one shot each to solve the required number of problems, while the rest of the team members need to order exactly three shots each to solve the required number of problems for them.

I. Open BSUIR
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Hello, my name is Steve. I invite you to the open olympiad at BSUIR. Take note of the coordinates: the star is called the Sun, and the planet is the third from the star. The olympiad will be attended by $$$n$$$ teams from the entire Milky Way galaxy, and your team will be the $$$n + 1$$$-th. Oh, and don't forget to come up with a problem, as this is an open olympiad and each team must propose exactly one problem. The olympiad will take place outdoors, and yes, for solving each problem your team will receive a balloon. But remember, during the olympiad it is forbidden to communicate with other participants and leave the olympiad area, otherwise the team will be disqualified. Let the strongest win, or rather the one who solves at least one more problem than all the other teams.

Steve has given you a certain list. This list contains information about each of the $$$n$$$ teams: $$$s_i$$$ — the strength of the $$$i$$$-th team, $$$w_i$$$ — the total weight of the $$$i$$$-th team, and $$$d_i$$$ — the difficulty of the problem proposed by the $$$i$$$-th team. According to the olympiad rules, for solving a problem of difficulty $$$x$$$, the team receives a balloon with a load capacity of $$$x$$$. Each team (including yours) always solves problems whose difficulty does not exceed the team's strength. The team always solves its own problem regardless of the difficulty. If at any moment the total load capacity of the balloons exceeds the weight of the team, it will take off into the air and leave the olympiad area, which in turn leads to disqualification.

You are wondering if you can win the olympiad by proposing a problem with a positive integer difficulty.

Input

The first line contains three integers $$$n$$$, $$$s_0$$$, and $$$w_0$$$ — the number of teams, the strength, and the weight of your team, respectively.

The next $$$n$$$ lines each contain three integers $$$s_i$$$, $$$w_i$$$, and $$$d_i$$$ — the strength and weight of the $$$i$$$-th team, and difficulty of the problem proposed by the $$$i$$$-th team.

$$$$$$1 \le n \le 10^5$$$$$$ $$$$$$1 \le s_0, s_i \le 10^5$$$$$$ $$$$$$1 \le w_0, w_i \le 10^9$$$$$$ $$$$$$1 \le d_i \le 10^5$$$$$$

Output

In a single line, output "Yes" if your team can win the olympiad. Otherwise, output "No".

Examples
Input
2 1 20
10 29 20
25 59 30
Output
Yes
Input
3 5 20
10 29 20
25 69 30
1 50 49
Output
No

J. Fashionable Suit
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Lorenzo is considered one of the most outstanding fashion designers of the last thousand years. Recently, Lorenzo presented his new, truly ingenious creation, a pearl in the fashion industry. He designed a suit entirely made of Velcro. The suit is so unique that no other designer has ever presented anything like it. Unfortunately, the suit turned out to be not very practical. When Lorenzo was heading to a fashion exhibition, he decided to save money and instead of a business-class taxi, he ordered an economy one. As a result, his suit stuck to the fabric interior of the car, and Lorenzo needed the driver's help to get out of the car. After overcoming this difficulty, another one suddenly arose. It turned out that at the exhibition, some of the walls were covered with fabric, and when Lorenzo leaned against one of them, he got stuck again. Now he can only move in three ways: rotate clockwise, rotate counterclockwise, or try to push off the wall with all his might, in which case Lorenzo will fly perpendicular to the wall until he hits another wall or flies out of the exhibition. To overcome this difficulty, he needs to either reach a regular wall (not covered with fabric) or fly out of the exhibition. Note that if Lorenzo sticks to a wall outside the exhibition, it does not mean that he has flown out of it. Unfortunately, since he left the taxi, Lorenzo has not had much strength left, so he wants to make the minimum number of movements to get out of this situation. He turned to you for help and asked to develop a plan so that he can move freely again (without leaning against the wall).

You have a plan of the exhibition, which is a grid of size $$$w$$$ cells in width and $$$h$$$ cells in height. The cells are numbered from top to bottom, left to right, starting from one. There are a total of $$$n$$$ fabric-covered walls and $$$m$$$ regular walls. You know to which wall and from which side Lorenzo got stuck. You need to find the minimum number of actions that Lorenzo needs to perform in order to move freely. There are three types of actions:

  1. Make one clockwise rotation. Then Lorenzo will move to the adjacent side of the wall, or to the opposite side of the wall if there is no adjacent wall.
  2. Make one counterclockwise rotation. Similar to the previous action.
  3. Push off the wall with all his might. In this case, Lorenzo will fly in the opposite direction from the wall, until he hits another wall or flies out of the exhibition.
Figure 1. Examples of possible actions
Input

The first line contains four integers $$$w$$$, $$$h$$$, $$$n$$$, and $$$m$$$ — the width and height of the exhibition, and the number of fabric-covered walls and regular walls, respectively.

The next $$$n$$$ lines contain two integers $$$x$$$ ($$$1 \le x \le w$$$) and $$$y$$$ ($$$1 \le y \le h$$$) and one character $$$t$$$ — the coordinates of the cell and its boundary where the fabric-covered wall is located. The character $$$L$$$ means that the wall is located on the left boundary, $$$R$$$ — on the right, $$$U$$$ — on the top, and $$$D$$$ — on the bottom.

The next $$$m$$$ lines contain the description of regular walls in the same format.

The last line contains two integers $$$sx$$$ ($$$1 \le sx \le w$$$) and $$$sy$$$ ($$$1 \le sy \le h$$$) and one character $$$st$$$ — the coordinates of the cell and its boundary to which Lorenzo got stuck. It is guaranteed that Lorenzo got stuck to a fabric-covered wall.

It is guaranteed that each wall cannot be both fabric-covered and regular (even different sides). Also, note that for example, "1 1 D" and "1 2 U" describe the same wall.

$$$$$$1 \le w, h \le 10^5$$$$$$ $$$$$$1 \le n \le 5 \cdot 10^5$$$$$$ $$$$$$0 \le m \le 5 \cdot 10^5$$$$$$ $$$$$$n + m \le 5 \cdot 10^5$$$$$$

Output

In the first line, output "No" if Lorenzo cannot free himself.

Otherwise, in the first line, output "Yes", and in the next line, output a string describing Lorenzo's route.

The symbol ">" indicates a clockwise rotation, "<" indicates a counterclockwise rotation, and "^{}" means that Lorenzo needs to push off the wall. If there are multiple possible answers, you need to output any of them consisting of the smallest number of actions.

Examples
Input
1 1 3 1
1 1 L
1 1 R
1 1 D
1 1 U
1 1 D
Output
Yes
^
Input
1 1 3 1
1 1 L
1 1 R
1 1 D
1 1 U
1 1 L
Output
Yes
<
Input
2 2 8 0
1 1 U
2 1 U
1 1 L
1 2 L
2 1 R
2 2 R
2 2 D
1 1 D
1 1 U
Output
Yes
^>^
Input
1 1 3 0
1 1 U
1 1 D
1 1 L
1 1 D
Output
Yes
>^
Input
1 1 4 0
1 1 U
1 1 D
1 1 L
1 1 R
1 1 L
Output
No
Note
Figure 2. Visualization for test examples 1-3

K. Starry Sky
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

How great it is to take a walk in the fresh air at night and gaze at the constellations in the sky! This time, you have decided to prepare and study the map of the starry sky. The map consists of $$$n$$$ points on the plane, where the $$$i$$$-th point is located at coordinates $$$(x_i, y_i)$$$. Also, the map includes $$$m$$$ segments connecting certain pairs of points. A connected set of points forms a constellation, and it is guaranteed that each constellation does not contain cycles.

You want to take exactly one rectangular photograph and count how many connected sets of points will be in this photograph. Let's call such sets of points imaginary constellations, as they may not coincide with the original constellations on the map, since constellations may be partially visible, and some may be divided into several imaginary constellations.

Unfortunately, your camera is broken, so each time it randomly takes a rectangular area. For this, the camera independently selects two coordinates (not necessarily integers) $$$x_a$$$ and $$$x_b$$$ uniformly at random on the interval $$$[x_{\min}, x_{\max}]$$$. Similarly, it selects two coordinates $$$y_a$$$ and $$$y_b$$$ on the interval $$$[y_{\min}, y_{\max}]$$$. As a result, the photograph includes all points $$$(x_i, y_i)$$$ for which the conditions $$$\min \{ x_a, x_b \} \le x_i \le \max \{ x_a, x_b \}$$$ and $$$\min \{ y_a, y_b \} \le y_i \le \max \{ y_a, y_b \}$$$ are satisfied.

A segment connecting a pair of points appears in the photograph only if both of its ends are also on the photograph.

You are interested in the mathematical expectation of the number of imaginary constellations in the snapshot.

Input

The first line contains six integers $$$n$$$, $$$m$$$, $$$x_{\min}$$$, $$$x_{\max}$$$, $$$y_{\min}$$$, $$$y_{\max}$$$ — the number of points on the star map and the number of straight segments connecting points.

The second line contains $$$n$$$ integers $$$x_i$$$ — the $$$x$$$-coordinate of the $$$i$$$-th star.

The third line contains $$$n$$$ integers $$$y_i$$$ — the $$$y$$$-coordinate of the $$$i$$$-th star.

The fourth line contains $$$m$$$ integers $$$a_i$$$ — the number of the star connected at one end of the $$$i$$$-th segment.

The fifth line contains $$$m$$$ integers $$$b_i$$$ — the number of the star connected at the other end of the $$$i$$$-th segment.

$$$$$$1 \le m \lt n \le 10^5$$$$$$ $$$$$$0 \le x_{\min} \lt x_{\max} \le 10^9, 0 \le y_{\min} \lt y_{\max} \le 10^9$$$$$$ $$$$$$0 \le x_i, y_i \le 10^9$$$$$$ $$$$$$1 \le a_i, b_i \le n$$$$$$ $$$$$$a_i \ne b_i$$$$$$

It is guaranteed that all points have distinct coordinates.

Output

Let $$$p$$$ be the mathematical expectation of the number of imaginary constellations in the photograph. It can be shown that the answer can be represented as $$$\frac{a}{b}$$$, where $$$a$$$ and $$$b$$$ are coprime integers ($$$b \not\equiv 0 \pmod{10^9+7}$$$). Here, $$$b^{-1}$$$ denotes an integer for which $$$b \cdot b^{-1} \equiv 1 \pmod{10^9+7}$$$. Output the value $$$a \cdot b^{-1}$$$ modulo $$$10^9+7$$$.

Examples
Input
2 1 0 3 0 3
1 2
1 2
1
2
Output
456790127
Input
2 1 0 2 0 2
1 3
1 3
1
2
Output
250000002
Input
12 8 0 16 0 8
1 5 1 5 6 8 10 6 11 11 15 15
1 7 7 1 7 4 7 1 1 7 7 1
1 3 5 6 6 9 9 11
2 4 6 7 8 10 11 12
Output
286376956