PSUT JCPC Qualification 2026
A. MrMoon creates Lucky Number Seven Command
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
"If you toss a coin and call heads, your probability of winning is 50 If you toss a coin 7 times and keep calling heads, your probability of winning is about 99 everything is part skill, part luck. Keep tossing the coin. Good luck"
— the poet

MrMoon is investigating the popularity of the infamous Pxl bot and wants to implement a new feature called the $$$Lucky Number Seven$$$ command since $$$7$$$ is Moon's favorite number.

This command just print the number 7.

Can you help MrMoon implement this command?

Input

no input is given

Output

Print the number $$$7$$$

Example
Input
no input
Output
7

B. Moon creates seal backflips
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
"As you grow older, you will discover that you have two hands - one for helping yourself, the other for helping others."
— the poet

You are given two non-negative integers $$$a$$$ and $$$b$$$, and an integer $$$k$$$.

Your task is to find the maximum non-negative integer $$$c$$$ such that $$$c \lt 2^{60}$$$ and it satisfies the following two conditions:

  • The number of set bits (1s) in the binary representation of $$$c \oplus a$$$ is less than or equal to $$$k$$$;
  • The number of set bits (1s) in the binary representation of $$$c \oplus b$$$ is less than or equal to $$$k$$$.

Here, $$$\oplus$$$ denotes the bitwise XOR operation.

Since the maximum value of $$$c$$$ can be large, print the maximum valid $$$c$$$ modulo $$$10^9 + 7$$$. If no such $$$c$$$ exists, print -1.

Input

The first line contains a single integer $$$T$$$ ($$$1 \le T \le 10^4$$$) — denotes the number of test cases.

The only line of each test case contain three integers $$$a$$$, $$$b$$$, and $$$k$$$ ($$$0 \le a, b \lt 2^{60}$$$, $$$0 \le k \le 60$$$).

Output

For each test case, output a single integer: the maximum possible valid value for $$$c$$$. Since the maximum value of $$$c$$$ can be large, print the maximum valid $$$c$$$ modulo $$$10^9 + 7$$$.

If no such integer $$$c$$$ exists, output $$$-1$$$.

Example
Input
3
5 3 2
7 0 1
0 0 60
Output
268198259
-1
536396503

C. Moon creates the Perfect Grid
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
"Just doing the thing repeatedly badly will produce better results than stressing about perfecting something you don't have the skill to prefect yet "
— the poet

Moon is analyzing an $$$n \times m$$$ binary grid (a grid containing only 0s and 1s). Moon calls the grid perfect if it satisfies the following condition:

for every cell at row $$$i$$$ and column $$$j$$$, the XOR sum of all elements in the $$$i$$$-th row and all elements in the $$$j$$$-th column is exactly equal to the value of the cell itself.

Formally, a grid $$$A$$$ is perfect if for all $$$1 \le i \le n$$$ and $$$1 \le j \le m$$$:

$$$$$$\left( \bigoplus_{k=1}^{m} A_{i,k} \right) \oplus \left( \bigoplus_{k=1}^{n} A_{k,j} \right) = A_{i,j}$$$$$$

such that $$$\oplus$$$ denotes the XOR bitwise operation (Note: The element $$$A_{i,j}$$$ is included in both the row's XOR sum and the column's XOR sum.)

Given the dimensions $$$n$$$ and $$$m$$$, Moon needs your help to find the total number of perfect binary grids. Since the answer can be massive, output it modulo 998244353.

Input

The first line contains an integer $$$T$$$ ($$$1 \le T \le 2 \cdot 10^5$$$) — denotes the number of test cases.

Each test case consists of a single line containing two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 10^{18}$$$) — denotes the number of rows and columns of the grid.

Output

For each test case, output a single integer on a new line: the number of perfect grids modulo 998244353.

Example
Input
3
2 4
1 3
1 5
Output
1
4
16

D. Moon creates Laser Gun
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
"He who fights with monsters should see to it that he himself doesn't become a monster "
— the poet

Moon is a legendary warrior renowned for his devastating signature technique: a continuous, sweeping energy beam. Moon is currently facing off against a formidable enemy in a combat trial, abu Ibrahim, and you need to calculate exactly how much damage his attack will deal.

The battle takes place on a 2D plane. Moon stands firmly at the origin $$$(0, 0)$$$, initially facing the direction vector $$$(x_0, y_0)$$$. Moon unleashes his charged beam attack, which lasts for $$$t$$$ units of time.

As Moon channels the overwhelming energy, he rotates counter-clockwise at a constant rate of 1 radian per unit of time. This means Moon completes a full circle counter-clockwise every $$$2\pi$$$ units of time.

Consider a ray extending from $$$(0, 0)$$$ toward the direction Moon is currently facing. The attack's area of effect includes all points whose perpendicular distance to this central ray is at most $$$d$$$.

The enemy, abu Ibrahim, is represented as a strictly convex polygon on the battlefield. If the enemy's shape shares any common points with the attack's area of effect, it will suffer $$$1$$$ unit of continuous damage per unit of time of exposure.

Your task is to calculate the total damage the enemy incurs in the first $$$t$$$ units of time.

Input

The first line contains five integers $$$n$$$, $$$x_0$$$, $$$y_0$$$, $$$d$$$, and $$$t$$$ ($$$3 \le n \le 100$$$, $$$-10^4 \le x_0, y_0 \le 10^4$$$, $$$x_0^2 + y_0^2 \gt 0$$$, $$$1 \le d, t \le 10^4$$$) — denotes the number of vertices of the enemy's shape, the coordinates defining Moon's initial directional vector $$$(x_0, y_0)$$$, the beam's width parameter $$$d$$$, and the total attack duration $$$t$$$.

The following $$$n$$$ lines describe the enemy's shape. The $$$i$$$-th line contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$-10^4 \le x_i, y_i \le 10^4$$$) — denotes the coordinates of the $$$i$$$-th vertex of the polygon.

It is guaranteed that:

  • The $$$n$$$ vertices are provided in strictly counter-clockwise order;
  • The polygon is strictly convex, meaning no three vertices are collinear;
  • The enemy's shape remains entirely outside Moon's immediate vicinity. Formally, no point inside or on the boundary of the polygon shares any common points with a circle of radius $$$d$$$ centered at $$$(0,0)$$$.
Output

Output one line containing one real number, indicating the damage the enemy incurs in the first $$$t$$$ units of time.Your answer will be considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$.

Formally speaking, suppose that your output is $$$a$$$ and the jury's answer is $$$b$$$, your output is accepted if and only if $$$\frac{\vert{}a-b\vert{}}{\max(1, \vert{}b\vert{})} \le 10^{-6}$$$.

Examples
Input
3 1 0 1 1
1 2
2 1
2 2
Output
1.000000000000
Input
4 1 0 1 2
5 -2
7 -2
7 2
5 2
Output
0.567285838194
Note

for the first test case here is what nano banana think it looks like :D

E. Moon creates a pocket gift
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
"Are you willing to sprint, when the distance is unknown?"
— the poet

Moon recently received a string $$$S$$$ from his friends. The string consists only of the characters 0, 1, and 2.

Moon thinks the string is too long and wants to compress it to put it in his pocket. He can perform an arbitrary number of operations on the string. In each operation, he can choose one of the following actions:

  • Change any 2 into a 0 or a 1;
  • Choose two adjacent 0s, erase them, and concatenate the remaining parts of the string;
  • Choose two adjacent 1s, erase them, and concatenate the remaining parts of the string.;

Help Moon calculate the minimum possible length of the string he can achieve after applying some number of operations.

Input

The first line contains a single integer $$$T$$$ $$$(1 \le T \le 10^4)$$$ — denotes the number of test cases.

The first and only line of each test case contains a string $$$S$$$ $$$(1 \le |S| \le 2 \cdot 10^5)$$$ consisting only of characters 0, 1, and 2 — denotes the string that moon received as a gift.

It is guaranteed that the sum of $$$\vert{}S\vert{}$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$.

Output

For each test case, output a single integer — the minimum sequence length Moon can achieve.

Example
Input
5
0110101
01020102
0000021111
1012121010
0100202010
Output
3
4
0
6
0

F. Moon creates Moon-Bahn
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output
"YOU CAN NEVER CROSS THE OCEAN UNTIL YOU HAVE THE COURAGE TO LOSE SIGHT OF THE SHORE
— the poet

Moon is currently living in Munich and relies on the city's extensive Moon-Bahn (subway) system to get around.

The Moon-Bahn system consists of $$$n$$$ stations, numbered 1 to $$$n$$$, and $$$k$$$ directed subway lines, numbered 1 to $$$k$$$. Subway line $$$i$$$ travels through a specific sequence of $$$p_i$$$ stations: $$$x_{i,1}, x_{i,2}, \dots, x_{i,p_i}$$$.

Traveling on line $$$i$$$ from station $$$x_{i,j}$$$ directly to the next station $$$x_{i,j+1}$$$ takes $$$w_{i,j}$$$ units of time. Because Munich is a bustling city, many lines intersect at various stations, allowing passengers to transfer.

However, transferring takes time. To avoid any ambiguity in the station maps: if Moon is at a station on line $$$X$$$ and wants to transfer to line $$$Y$$$ (which also passes through this station), it will cost him exactly $$$B_X \cdot A_Y$$$ units of time. Here, $$$B_X$$$ is the transfer-out coefficient of his current line $$$X$$$, and $$$A_Y$$$ is the transfer-in coefficient of his new line $$$Y$$$.

After transferring, Moon remains at the same station but is now riding line $$$Y$$$. Moon starts his journey at station 1. He can initially board any line that passes through station 1 with zero transfer cost.

Please help Moon find the minimum time required to reach every other station $$$s$$$ ($$$2 \le s \le n$$$) from station 1. It is guaranteed that all stations are reachable from station 1.

Input

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le k \le 2 \cdot 10^5$$$) — denotes the number of stations and the number of subway lines.

The second line contains $$$k$$$ integers $$$A_1, A_2, \dots, A_k$$$ ($$$1 \le A_i \le 10^6$$$) — denotes the transfer-in coefficients for the lines.

The third line contains $$$k$$$ integers $$$B_1, B_2, \dots, B_k$$$ ($$$1 \le B_i \le 10^6$$$) — denotes the transfer-out coefficients for the lines.

For the following $$$k$$$ lines, the $$$i$$$-th line describes subway line $$$i$$$. It starts with an integer $$$p_i$$$ ($$$2 \le p_i \le n$$$) — denotes the number of stations line $$$i$$$ travels through.

This is followed by $$$2p_i - 1$$$ integers $$$x_{i,1}, w_{i,1}, x_{i,2}, w_{i,2} \dots, x_{i,p_i}$$$ ($$$1 \le x_{i,j} \le n$$$, $$$1 \le w_{i,j} \le 10^9$$$) — where $$$x_{i,j}$$$ is the $$$j$$$-th station on the line, and $$$w_{i,j}$$$ is the travel time to the next station.

The stations traveled through by any single subway line are distinct.

It is guaranteed that $$$\sum_{i=1}^{k} (p_i - 1) \le 2 \cdot 10^5$$$.

Output

Output one line containing $$$n - 1$$$ integers $$$d_2, d_3, \dots, d_n$$$ separated by a space, where $$$d_i$$$ is the minimum time cost to travel from station 1 to station $$$i$$$.

Example
Input
6 3
1 5 1
5 5 1
3 1 2 2 3 3
3 5 1 2 1 4
3 3 4 5 4 6
Output
2 5 21 14 18
Note

here is what Nano Banana thinks how the test case looks like

G. Moon creates a Pxls
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
"Move the body before the sword"
— the poet

Moon built a new factory with $$$s$$$ workbenches. He needs to build $$$n$$$ toy robots.

Building any robot takes exactly $$$1$$$ hour and occupies exactly one workbench during that time. Each robot also has a strict deadline $$$d$$$ (in hours) by which it must be completely finished and shipped.

Here is the catch: some robots are special and require Moon to use his Magic Mond Tool. Because he only made one Mond Tool, he can build at most one special robot per hour. These special robots still require an empty workbench, just like the normal ones. The normal robots can not use the tool.

Moon can build as many normal robots at the exact same time as he wants, as long as he has an empty workbench for each of them.

Moon needs to know: is it possible to schedule his work so that every single robot is finished by its deadline?

Input

The first line contains two integers $$$s$$$ ($$$1 \le s \le 5 \cdot 10^4$$$) and $$$n$$$ $$$(1 \le n \le 10^5)$$$ — denotes the number of workbenches and the number of robots to be crafted.

Following this are n lines, one for each robot, each line contains an integer $$$d$$$ $$$(1 \le d \le 10^9)$$$ and a character $$$t$$$ — denotes the deadline and If $$$t$$$ is $$$y$$$ (case sensitive), the robot requires the Mond Tool. If $$$t$$$ is $$$n$$$ (case sensitive), it does not.

Output

If it is possible to allocate the robots and the Mond Tool to meet all deadlines, output Yes. Otherwise, output No.

In the output, the YESs and NOs are case-insensitive, meaning that outputs such as yEs and nO are valid.

Examples
Input
3 7
2 y
2 n
5 y
1 n
5 n
2 y
1 n
Output
yes
Input
2 7
2 y
2 n
5 y
1 n
5 n
2 y
1 n
Output
no

H. Moon creates Electi
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
"Remember,The wolf on the hill is never as hungry as the wolf climbing the hill"
— the poet

Head Coach Moon is completely fed up with arbitrary power rankings. He believes that changes in team rankings should be strictly evidence-based.

Initially, there are $$$n$$$ teams, ranked from $$$1$$$ (best) to $$$n$$$ (worst). Each team is simply named after its starting rank (Team 1, Team 2, ..., Team $$$n$$$).

When a game occurs between two teams, Moon updates the rankings according to these rules:

  • No Upset: If the higher-ranked team wins, the rankings do not change. Moon sees no evidence that the current order is wrong;
  • Upset: If a lower-ranked team (the underdog) defeats a higher-ranked team (the favorite), the losing favorite drops down to the underdog's exact position. Every team that was ranked between them moves up exactly one spot to fill the gap.

Given a list of $$$m$$$ match results in the order they were played, determine the final team rankings after all matches have been processed.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 100$$$) — denotes the number of teams and the number of games played.

Each of the next $$$m$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$) — denotes indicating that Team $$$u$$$ defeated Team $$$v$$$ in that match.

Output

Print a single line containing $$$n$$$ space-separated integers representing the final ranking of the teams, from 1st place to $$$n$$$-th place.

Example
Input
5 3
4 1
3 1
5 3
Output
2 4 1 5 3

I. Moon creates Mond
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
"Flip bits, not burgers"
— the poet

Moon just created his robot, Mond, and his pronouns are med/median, Mond's task is to solve the problem Moon gave him.

Moon has $$$n$$$ cards are placed in a row, where $$$n$$$ is an odd number. Each card has numbers written on both sides. On the $$$i$$$-th card, $$$a_i$$$ is facing up and $$$b_i$$$ is facing down.

Moon wants to maximize the median of all the numbers that are facing up. In order to achieve this, he can do the following operation at most once:

  • Choose an interval $$$[l, r]$$$ and flip all the cards in the interval. After flipping the cards, $$$b_i$$$ will be facing up and $$$a_i$$$ will be facing down for $$$i \in [l, r]$$$.

Please help Moon to implement this feature in Mond and calculate the median of all the numbers that are facing up under his optimal strategy.

Note: that the median of a sequence of numbers is the $$$\frac{n+1}{2}$$$-th largest number in the sequence.

Input

The first line contains two integers $$$n$$$ ($$$1 \le n \lt 3 \cdot 10^5, n \pmod 2 = 1$$$) — denotes the number of cards.

Each of the next $$$n$$$ lines contains 2 integers $$$a_i, b_i$$$ ($$$1 \le a_i, b_i \le 10^9$$$) — denotes the initial number that is facing up and the initial number that is facing down for each card.

Output

Output one integer, denoting the median of all the numbers that are facing up.

Examples
Input
5
3 6
5 2
4 7
6 4
2 8
Output
6
Input
5
1 10
1 10
1 10
10 1000
10 1000
Output
10

J. Moon creates Luna Game
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
"You don't always have to hit the brakes, sometimes you just gotta let your foot of the gas"
— the poet

Moon possesses $$$r_1$$$ Stones, $$$s_1$$$ Blades, and $$$p_1$$$ Scrolls. Conversely, Luna holds $$$r_2$$$ Stones, $$$s_2$$$ Blades, and $$$p_2$$$ Scrolls.

The total number of cards is $$$n = r_1 + s_1 + p_1 = r_2 + s_2 + p_2$$$.

They play $$$n$$$ rounds. In each round, both players choose one card to play.

The game follows standard Rock-Paper-Scissors rules:

  • Stone beats Blade;
  • Blade beats Scroll;
  • Scroll beats Stone.

If Moon wins, the score increases by $$$1$$$. If Luna wins, the score decreases by $$$1$$$. If they tie, the score remains unchanged. Moon wants to maximize the final score, and Luna wants to minimize it.

Given the card counts for both, find the maximum and minimum possible scores.

Input

The first line contains a single integer $$$T$$$ ($$$1 \le T \le 10^4$$$) — denotes the number of test cases.

The first and only line of each test case contain seven integers $$$n, r_1, s_1, p_1, r_2, s_2, p_2$$$ (where $$$1 \le n \le 10^9$$$ and $$$ 0 \le r_1, s_1, p_1, r_2, s_2, p_2 \le n$$$) — denotes Moon's $$$r_1$$$ Stones, $$$s_1$$$ Blades, and $$$p_1$$$ Scrolls.And Luna holds $$$r_2$$$ Stones, $$$s_2$$$ Blades, and $$$p_2$$$ Scrolls.

Output

For each test case, output a single line containing two integers — denoting the maximum and minimum possible scores, respectively.

Example
Input
2
1 0 1 0 0 0 1
3 1 1 1 1 1 1
Output
1 1
3 -3
Note

In the first test case, Moon plays the Blade against Luna's Scroll. Blade beats Scroll, so Moon wins. Score is $$$+1$$$. Since Moon only has a Blade and Luna only has a Scroll, there is no other move to make. Moon must win, so the lowest possible score is still $$$+1$$$.

K. Moon creates the office
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
"Assume something, and then see what results from it. If you run into a contradiction, then your assumption must be false."
— the poet

There is a queue of $$$N$$$ people numbered from $$$1$$$ to $$$N$$$ waiting to submit their requests at Moon's office.

Initially, the queue is formed in ascending order of their number, meaning you start with the first person from the $$$N$$$ people then you see the second and so on. Each person has a request that requires $$$R_i$$$ units of time for Moon to process.

Moon can process a maximum of $$$M$$$ units of time per person in one turn. If a person's request requires more time than $$$M$$$, they must go to the back of the queue and wait for their turn again. A person leaves the queue once their entire request has been processed.

Your task is to help him determine the order in which the people leave the queue after their requests are fully processed.

Input

The first line of the input gives you two space-separated integers $$$N, M$$$ ($$$1 \le N \le 10^6$$$, $$$1 \le M \le 10^9$$$) — denotes the number of people and units of time per person in one turn.

The next line contains $$$N$$$ space-separated integers $$$R_i$$$ ($$$1 \le R_i \le 10^5$$$) — denotes the $$$ith$$$ person has a request that requires $$$R_i$$$ units of time for the office to process

Output

Output one line, a space-separated list of integers that denote the order in which the people leave the queue.

Examples
Input
5 10
2 4 6 8 10
Output
1 2 3 4 5
Input
4 5
10 11 10 11
Output
1 3 2 4

L. Moon creates Mex Grid
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output
"Every 2nd count"
— the poet

Moon is fascinated by the MEX (minimum excluded) operation. Today, he is challenging himself with a grid construction puzzle.

He is given two arrays of integers, $$$a$$$ and $$$b$$$. The length of array $$$a$$$ is $$$n$$$, and the length of array $$$b$$$ is $$$m$$$. Moon's task is to construct a matrix $$$C$$$ of dimensions $$$n \times m$$$ that satisfies all of the following strict conditions:

  • Every integer in the interval $$$[0, n \cdot m - 1]$$$ must appear in $$$C$$$ exactly once;
  • The MEX of the $$$i$$$-th row must be exactly $$$a_i$$$;
  • The MEX of the $$$j$$$-th column must be exactly $$$b_j$$$.

The $$$\operatorname{MEX}$$$ (Minimum EXcluded value) of an array is the smallest non-negative integer that is not in the array. For example:

  • The $$$\operatorname{MEX}$$$ of $$$[1, 2, 3]$$$ is $$$0$$$
  • The $$$\operatorname{MEX}$$$ of $$$[0, 1, 2]$$$ is $$$3$$$
  • The $$$\operatorname{MEX}$$$ of $$$[0, 1, 3]$$$ is $$$2$$$

Can you help Moon determine if such a matrix exists? If it does, you must also help him build one.

Input

The first line contains two positive integers $$$n$$$ and $$$m$$$ ($$$1 \le n \cdot m \le 10^5$$$) — denotes the dimensions of the grid and the lengths of the arrays $$$a$$$ and $$$b$$$.

The second line contains $$$n$$$ integers $$$a_1, \dots, a_n$$$ ($$$0 \le a_i \le 10^5$$$) — denotes the required MEX values for the rows.

The third line contains $$$m$$$ integers $$$b_1, \dots, b_m$$$ ($$$0 \le b_i \le 10^5$$$) — denotes the required MEX values for the columns.

Output

If there exists a valid matrix, output "Yes" case sensitive on the first line. Otherwise, output "No" case sensitive.

If the answer is "Yes", output $$$n$$$ additional lines, each containing $$$m$$$ integers, representing the matrix $$$C$$$. If there are multiple valid matrices, output any of them.

Examples
Input
2 2
2 0
1 0
Output
Yes
0 1 
2 3
Input
2 2
1 1
1 1
Output
No
Input
1 1
1
1
Output
Yes
0
Input
1 2
1
0 1
Output
No

M. Moon creates Light Binary Switches
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
"No lights, only instinct."
— the poet

Moon is experimenting with a system of linked binary switches. He starts with an initial sequence of $$$n$$$ bits, $$$a_1, \dots, a_n$$$, where every bit is initially set to $$$0$$$. He also has a target configuration in mind, represented by a sequence of $$$n$$$ bits, $$$b_1, \dots, b_n$$$.

To manipulate the sequence, Moon has access to a specific set of $$$m$$$ operations. Each operation is defined by a pair of indices $$$(i, j)$$$. Applying this operation simultaneously flips the state of both the $$$i$$$-th bit and the $$$j$$$-th bit (i.e., $$$a_i$$$ becomes $$$1 - a_i$$$ and $$$a_j$$$ becomes $$$1 - a_j$$$).

Moon can apply each of the available operations zero or multiple times, and in any order he chooses. Can you help Moon determine if it is possible to transform the initial sequence of all zeros into his target sequence $$$b$$$?

Input

The first line contains a single integer $$$n$$$ ($$$2 \le n \le 10^5$$$) — denotes the length of the binary sequence.

The second line contains $$$n$$$ integers $$$b_1, \dots, b_n$$$ ($$$0 \le b_i \le 1$$$) — denotes the target sequence of bits.

The third line contains a single integer $$$m$$$ ($$$1 \le m \le 10^5$$$) — denotes the number of available operations.

The following $$$m$$$ lines each contain two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \lt r_i \le n$$$) — denotes the indices representing an operation. It is guaranteed that no two operations are identical.

Output

output "YES" (without quotes) if it is possible, and "NO" (without quotes) otherwise.

You can output "YES" and "NO" in any case (for example, strings "yES", "yes" and "Yes" will be recognized as a positive response).

Examples
Input
5
1 1 0 1 1
3
1 3
3 4
2 5
Output
Yes
Input
2
0 1
1
1 2
Output
No