Winter Cup 7.0 Online Mirror Contest
A. Alibaba and Forty Thieves
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

In the vast and mysterious land of Arabia, the legendary Alibaba discovers a hidden cave filled with treasures beyond imagination. However, the cave holds a strange secret. It stores not only riches but also magical arrays, each locked by a unique pattern. Alibaba, along with his loyal companions, must now figure out how to unlock the secrets of these arrays, using clever tricks and reasoning.

You are given an array $$$A$$$ of $$$n$$$ integers, representing a magic sequence in the cave. Your task is to process $$$Q$$$ queries, which are of two types:

  • Type $$$1$$$ (Add Array): You are given an array $$$M$$$ of length $$$k$$$ that you need to store as a potential magical array. These arrays will later be compared against parts of the main array $$$A$$$.

  • Type $$$2$$$ (Match Occurrences): You are given two indices $$$l$$$ and $$$r$$$. Your goal is to count how many of the stored arrays match the pattern of occurrences of the subarray $$$A[l..r]$$$. An array $$$M$$$ matches if, for each unique element $$$X$$$ in all the arrays including $$$A$$$, the occurrence of $$$X$$$ in $$$A[l..r]$$$ is equal to the occurrence of $$$X$$$ in $$$M$$$.

For example, consider the array $$$A = [1, 2, 3, 3]$$$ and two stored arrays $$$M_1$$$ and $$$M_2$$$:

- $$$M_1 = [2, 3, 1, 3]$$$ — This array matches the subarray $$$A[1..4]$$$.

- $$$M_2 = [2, 3, 1, 3, 5]$$$ — This array does not match.

Input

The first line contains two integers $$$n$$$ and $$$Q$$$ $$$(1 \leq n \leq 10^5, 1 \leq Q \leq 2 \times 10^5)$$$ — the size of the array $$$A$$$ and the number of queries, respectively.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ $$$(0 \leq a_i \leq 10^9)$$$ — the elements of the array.

The next $$$Q$$$ lines contain queries of one of the following types:

  • Type $$$1$$$ (Add Array): The line contains two integers '$$$1$$$ $$$k$$$' $$$(1 \leq k \leq 10^6)$$$, indicating that the next line contains $$$k$$$ integers $$$b_1, b_2, \dots, b_k$$$ $$$(1 \leq b_i \leq 10^9)$$$. This array $$$M$$$ should be stored for future queries.

  • Type $$$2$$$ (Match Occurrences): The line contains three integers '$$$2$$$ $$$l$$$ $$$r$$$' $$$(1 \leq l \leq r \leq n)$$$.

Note:

  • The sum of $$$k$$$ over all queries doesn't exceed $$$10^6$$$.

  • The total number of distinct integers over ALL arrays does not exceed $$$100$$$.
Output

For each query of type 2, you need to output how many stored arrays match the pattern of occurrences of the subarray $$$A[l..r]$$$.

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

B. Bad Sindibad
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

After his seven great voyages and accumulating unimaginable wealth, Sindibad had many servants, from humans to Jinns, some of whom he tricked many times through his past adventures. They serve him well, so Sindibad refuses to free any of them. However, he becomes wary of their potential rebellion against him. So, he swears to free his Jinn servants if they achieve one task. He wants to give them a task that would seem simple but may take them a long time to finish.

Given a grid of length $$$n$$$ and width $$$4$$$, and this specific shape (shown in the image below), his Jinn servants must tile the entire grid using copies of this shape.

The shape can be rotated or flipped in any way but must completely fit within the grid. Each grid cell must be covered exactly once by a shape (no overlaps or empty cells) and every tile must have an adjacent tile to which they form a rectangle.

Determine how many distinct ways this grid can be fully tiled using copies of this shape.

Input

The input contains a single integer $$$n, ( 1 \leq n \leq 40 )$$$ — the length of the grid.

Output

Output a single integer — the number of distinct ways the shape can be placed within the grid.

Example
Input
3
Output
4

C. The Tale of the Magical Lantern Grid
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In the heart of Agrabah, as the holy month of Ramadan began, the city came alive with the scent of spices, the sound of prayers, and the warmth of community. To celebrate this sacred time, the wise and beloved Sultan decided to create a grand display of lanterns symbolizing unity and harmony.

The Sultan commissioned an $$$n \times n$$$ mystical grid, where each lantern at position $$$(i, j)$$$ carried a special meaning. He explained to his trusted advisor, Aladdin, that the brightness of each lantern depended on the mathematical relationship between its row $$$i$$$ and column $$$j$$$.

The Rule of the Lanterns

  • If $$$i$$$ and $$$j$$$ are coprime (i.e., their greatest common divisor is $$$1$$$), the lantern shines brightly with a value of $$$i \times j$$$, symbolizing purity and harmony.
  • If $$$i$$$ and $$$j$$$ are not coprime, the lantern remains dark with a value of $$$0$$$, representing the absence of unity.

Example: $$$n=3$$$

Aladdin, eager to assist, was given the task of calculating the total brightness of all the lanterns in the grid. The Sultan believed that this total brightness would reflect the collective spirit of Agrabah during Ramadan.

To ensure the result remains manageable, the total brightness should be computed modulo $$$10^9 + 7$$$.

Can you help Aladdin solve this challenge and determine the total brightness of the magical lantern grid?

Input

The first line contains the number of test cases t ($$$1\le t \le 10^5$$$). Each test case consists of a single integer $$$n$$$ ($$$1\le n \le 10^5$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2.10^5$$$

Output

For each test case, print the total brightness of the magical lantern grid.

Example
Input
2
1
3
Output
1
23

D. Max Diversity, No Superiority
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Iceberg House, a trading house, is a highly desirable workplace for young scholars thanks to its renowned reputation throughout the markets. Each year, Yessine receives a vast pool of apprenticeship seekers. In the past, he would select candidates arbitrarily. However, this year, he has learned from travelers along the Silk Road that trading houses with diverse knowledge and skills are more successful in negotiating profitable deals with merchants from distant lands.

To enhance diversity, Yessine has identified a list of $$$n$$$ skills. Each candidate has a proficiency score for each skill, ranging from $$$1$$$ (lowest proficiency) to $$$m$$$ (highest proficiency).

To ensure a diverse selection, Yessine will choose candidates such that no applicant is more skilled than another. However, if two or more candidates are equally skilled, then Yessine will only select one of them.

A candidate $$$A$$$ is more skilled than $$$B$$$ if, for every skill, candidate $$$A$$$ has a proficiency score greater than or equal to candidate $$$B$$$, and for at least one skill, candidate $$$A$$$ has a strictly higher proficiency score. Two candidates are equally skilled if they have exactly the same proficiency scores for all skills.

Yessine wants to maximize the number of young scholars while still adhering to the selection criteria described above.

The applicant pool is very large and contains every possible combination of skill scores. What is the maximum number of candidates Yessine can accept while ensuring no candidate is more skilled than another?

Since the answer can be large, output it modulo $$$M = 998244353$$$.

Input

The single line of the input contains two space separated integers:

  • $$$ n \ (1 \leq n \leq 10^3) $$$ — The number of skills
  • $$$ m \ (1 \leq m \leq 10^3) $$$ — The highest possible proficiency score for each skill.
Output

Output one integer, representing the desired answer modulo $$$998244353$$$

Examples
Input
10 10
Output
432457640
Input
3 20
Output
300
Input
100 100
Output
920143000
Input
200 200
Output
441305744

E. Swap Task
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In Sultan Malik's palace, there are $$$N$$$ antiques, each with a distinct value. Initially, the antiques are arranged randomly in the entrance of his palace.

Sultan Malik, known for his love of perfection, wishes to sort his antiques in ascending order of their values.

The Sultan is looking for a wise advisor, so he makes this task into a game. You can only sort the antiques using swaps. Moreover, there is another restriction: a swap is only allowed if one antique has a value strictly greater than a chosen threshold $$$K$$$, and the other has a value strictly lower than $$$K$$$.

Formally, given an array $$$A$$$ of $$$N$$$ distinct integers, you want to sort it with the following operation:

  • $$$swap(A_i, A_j)$$$ only if $$$A_i \gt K$$$ and $$$A_j \lt K$$$, where $$$K \ge 0$$$.

The Sultan will select the advisor who can find the smallest possible $$$K$$$ that allows the antiques to be sorted in increasing order.

Fankoush, aspiring to be the Sultan's advisor, asked for your help to determine $$$K$$$.

If there exists no such $$$K$$$, you must report $$$-1$$$ to Fankoush.

Input

The first line contains an integer $$$T$$$ denoting the number of test cases ($$$ 1 \le T \le 10^5 $$$). For each test case:

  • The first line contains an integer $$$N$$$, the size of the array ($$$ 2 \le N \le 10^5 $$$).
  • The second line contains $$$N$$$ distinct integers, the $$$i^{th}$$$ integer representing the array $$$A_i$$$ ($$$ 1 \le A_i \le 10^9 $$$).
It is guaranteed that the sum of $$$N$$$ over all test cases doesn't exceed $$$4.10^5$$$.
Output

Print the minimum possible $$$K$$$ or $$$-1$$$ if it is not possible.

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

F. Fawanis Ramadan
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Each year, Aziz Mansour, a local shopkeeper, lights up lanterns (fawanis) in the streets around his shop to celebrate Ramadan. The lanterns are represented by a string of bits, where $$$1$$$ symbolizes a lit lantern and $$$0$$$ symbolizes an unlit lantern.

To maintain tradition, the fawanis must follow a harmonious pattern: the number of $$$01$$$-substrings (a lit lantern followed by an unlit one) must be equal to the number of $$$10$$$-substrings (an unlit lantern followed by a lit one).

However, this year, Mansour has committed an error and the pattern may have become unbalanced. Your task is to help Mansour restore harmony to the lanterns by making the fewest changes.

In one change, you may flip any bit in the string (change a $$$1$$$ to $$$0$$$ or vice versa) to achieve the balanced pattern.

Input

The first line contains a number $$$N$$$: the length of the string. $$$2\le N \le 10^6$$$

The second line contains a string $$$S$$$, the string modeling the lanterns

Output

Output two lines:

  • The first line contains the number $$$k$$$ of bits you flipped
  • The second line contains $$$k$$$ space separated denoting the indexes ($$$0$$$-based) of the bits you flipped
If no bits should be flipped, simply output $$$0$$$
Examples
Input
2
10
Output
1
0
Input
3
101
Output
0

G. Guess The Permutation
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem.

Sultan Shahrayar has $$$n$$$ advisors, numbered from $$$1$$$ to $$$n$$$. One time he was bored, so he arranged them in a line, ordered from the wisest to the least wise. To test your intelligence, he brings you to his castle and challenges you to guess the exact order of the advisors. To help you, he allows you to ask $$$20000$$$ questions. In each question, you can pick a number $$$x$$$ and Shahrayar will tell you whether the number of inversions of the order is more or less or equal to $$$x$$$.

A pair $$$(i, j)$$$ is called an inversion in an array $$$A$$$ of length $$$n$$$ if:

  • $$$1 \le i \lt j \le n$$$ and $$$A_i$$$ > $$$A_j$$$.

After each question, the order of the advisors is rotated to the right.

For example, if the initial order is $$$[4, 1, 3, 2]$$$, the inversions are $$$(4,1)$$$, $$$(4,3)$$$, $$$(4,2)$$$, and $$$(3,2)$$$, resulting in a total of $$$4$$$ inversions. After one question, the order becomes $$$[2, 4, 1, 3]$$$ and the number of inversions is $$$3$$$.

Interaction

The interaction starts after reading a single integer $$$n$$$ $$$(2 \le n \le 1000)$$$ - the length of the permutation.

To ask a question, print "$$$?$$$ $$$x$$$" $$$(0 \le x \le n^2)$$$, then read the answer.

  • You will receive $$$ \lt $$$ if the number of inversions of the order is less than $$$x$$$.

  • You will receive $$$=$$$ if the number of inversions of the order is equal to $$$x$$$.

  • You will receive $$$ \gt $$$ if the number of inversions of the order is greater than $$$x$$$.
If you guess the permutation, print "$$$!$$$ $$$p_{1}$$$ $$$p_{2}...p_{n}$$$"
Example
Input
3

<

<

>

=
Output

? 2

? 2

? 2

? 1

! 1 3 2
Note

You have to guess the initial order, not the order after the questions.

After printing a query or the answer, do not forget to output an end-of-line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

- fflush(stdout) or cout.flush() in C++;

- System.out.flush() in Java;

- stdout.flush() in Python;

H. Hamming Guess
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem.

Aladdin has found the magical lamp and awakened the Genie inside it. He wished to become the richest man in the kingdom. The Genie agreed to grant Aladdin his wish and said he would do so by granting him $$$n$$$ golden coins. However, there was one condition for the wish to come true, Aladdin must guess the number. The Genie told Aladdin that he has at most $$$29$$$ tries to guess $$$n$$$, and that the number of golden coins is at least $$$1$$$ and at most $$$10^9$$$.

To find the secret number, Aladdin needs to make guesses, where in each guess he proposes a number. After each guess, the Genie will reveal to Aladdin the Hamming distance between the guess and $$$n$$$.

The Hamming distance between $$$2$$$ integers is the number of bits that are different at the same position in both numbers in their binary representation. For example, the Hamming distance between $$$9$$$ and $$$14$$$ is $$$3$$$.

Aladdin really wants to get rich. Can you help him uncover the number of golden coins before all his wishes are gone?

Interaction

To make a query, you have to print a line "$$$?$$$ $$$x$$$" $$$(0 \le x \le 10^{9})$$$

After each query, read a single integer $$$k$$$ $$$(0 \le k \le 30)$$$ – the Hamming distance between $$$n$$$ and $$$x$$$.

When you find $$$n$$$, print a line "$$$!$$$ $$$n$$$". Printing $$$n$$$ is not counted as one of 29 operations.

Example
Input

3

4

2

0
Output
? 24

? 55

? 8

? 4

! 4
Note

After printing a query or the answer, do not forget to output an end-of-line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

- fflush(stdout) or cout.flush() in C++;

- System.out.flush() in Java;

- stdout.flush() in Python;

I. Vanishing Island
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In the enchanting realm of Alf Layla w Layla, there lies a remote island where rising sea levels, due to melting ice caps, are increasing the water level by $$$1mm$$$ each year.

The island inhabitants, with a knack for a living simply and no known talent for bridge-building, are worried about their island splitting into separate landmasses. They joke that if their island splits, they might need to start a swimming club just to visit neighbors! Thus, they're keen to find out in which year that will happen.

Fortunately, the wise sorceress Zahra has foreseen this calamity. Using her mystical powers, she has devised a way to predict the fate of the island. She has transformed the island's topography into an $$$n \times m$$$ grid, where each cell represents the elevation above sea level in millimeters (cells with $$$0$$$ elevation initially represent sea). Zahra's magic allows her to simulate the rising sea levels year by year, revealing how the island will change over time.

For the purposes of this problem, an island is considered divided if there exists one path of sea ($$$0$$$ elevation) that separates the island into distinct land masses.

Note that two cells are considered part of the same landmass only if they are connected by their sides (up, down, left, or right).

Furthermore, any land that reaches an elevation below $$$0$$$ is considered submerged and thus treated as sea, even if it doesn't have direct contact with the existing sea areas at that point in time.

If no division occurs, the entire island will eventually sink below sea level.

Zahra's prediction depends on this simulation. She tasks you with analyzing the grid, year by year, as the sea level rises, to determine the precise moment when the island first splits into separate landmasses.

Print the year when the island is first divided into two or more landmasses. If no division occurs until the moment the whole island sinks undersea, print $$$-1$$$.

Input

The first line contains $$$2$$$ integers $$$n$$$ and $$$m$$$ $$$(3 \le n,m \le 10^3)$$$ respectively the length and width of the map containing the island.

Then a grid of $$$n \times m$$$ numbers will follow representing the current topology of the island.

Each number represents the elevation of that point above the sea level while $$$0$$$ represents points already submerged by the sea ($$$0 \leq elevation(i,j) \leq 10^9$$$).

Output

Print the year when the island is first divided into two or more land masses. If no division occurs until the moment the whole island sinks undersea, print $$$-1$$$.

Examples
Input
5 6
0 0 0 0 0 0
0 2 2 1 0 0
0 0 1 1 2 0
0 0 0 2 3 0
0 0 0 0 0 0
Output
1
Input
5 5
0 0 0 0 0
0 0 1 0 0
0 4 2 2 0
0 0 3 0 0
0 0 0 0 0
Output
2
Note

Below is a simulation of the $$$1st$$$ test example

The answer is $$$1$$$ since after $$$1$$$ year the island will be divided into $$$2$$$ isolated landmasses.

J. Rock Paper Scissors
time limit per test
6 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

During the holy month of Ramadan, Rami and Yassine have a special tradition. Every night, after breaking their fast at iftar, they head to their favorite coffee place to engage in friendly games while waiting for suhoor. One evening, they decide to play a modified version of Rock-Paper-Scissors as a card game.

There are only three types of cards: Rock, Paper, and Scissors.

  • Rami starts with $$$R_1$$$ Rock cards, $$$P_1$$$ Paper cards, and $$$S_1$$$ Scissors cards.
  • Yassine starts with $$$R_2$$$ Rock cards, $$$P_2$$$ Paper cards, and $$$S_2$$$ Scissors cards.
  • The total number of cards for Rami is $$$n_1 = R_1 + P_1 + S_1$$$, and for Yassine, it is $$$n_2 = R_2 + P_2 + S_2$$$.
  • Both players know the composition of each other's deck before the game starts.
  • Before playing, each player privately shuffles their deck, so that it is impossible for the opponent to gain any insight into the order of their cards.

The game proceeds in turns as follows:

  1. Card Selection:
    • Each player privately inspects his deck, and chooses a single card.
    • The selection is made simultaneously, and neither player knows the opponent's choice beforehand.
  2. Card Reveal & Outcome:
    • Both players reveal their chosen card at the same time.
    • The result follows standard Rock-Paper-Scissors rules:
      • Rock beats Scissors
      • Scissors beats Paper
      • Paper beats Rock
      • If both players select the same type, it is a draw.
  3. Card Handling:
    • If a player wins a round, their opponent's card is discarded permanently. The winning player keeps their card and returns it to their deck.
    • If the round is a draw, both players take back their respective cards.
  4. Winning Condition:
    • A player loses immediately if their deck no longer contains at least one of the three card types (Rock, Paper, or Scissors).
    • The game continues until one player loses.

Now both players play optimally, and fairly:

  • Both players play optimally, meaning they make decisions to maximize their probability of winning the game.
  • Both players play fairly, meaning they do not cheat, communicate, or exploit unintended mechanics.

Given the initial deck compositions $$$R_1, P_1, S_1$$$ for Rami and $$$R_2, P_2, S_2$$$ for Yassine, compute the probability of each player winning the game.

Input

A single line containing six integers $$$1 \leq R_1, P_1, S_1, R_2, P_2, S_2 \leq 18$$$.

It is guaranteed that: $$$$$$ 3 \leq \max(R_1 + P_1 + S_1, R_2 + P_2 + S_2) \leq 20 $$$$$$

Output

Print two floating-point numbers $$$0 \leq p_1, p_2 \leq 1$$$:

  • $$$p_1$$$: the probability that Rami wins the game
  • $$$p_2$$$: the probability that Yassine wins the game
Examples
Input
1 1 1 1 1 1
Output
0.5 0.5
Input
4 5 6 5 5 5
Output
0.482774 0.517226
Note

The first test case corresponds to a traditional rock paper scissor game. It can be proven that the optimal strategy for each player, is to choose any card, with the same probability.

K. Yet Another Swap Task
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Fankoush has successfully been recruited as the advisor to Sultan Malik.

In his first day, he faced a new challenge: Sultan Malik has an ancient letter containing an encrypted string $$$S$$$ of $$$N$$$ characters. The letters hold some important content. To restore it, the string must be sorted through a series of swaps.

Again, there is a restriction: characters $$$c_1$$$ and $$$c_2$$$ can only be swapped if a rule $$$(c_1, c_2)$$$ exists. At first, no rules exist, so Fankoush must create them.

Note that the rule $$$(c_1, c_2)$$$ is the same as the rule $$$(c_2, c_1)$$$.

To prove his skill, he must find the minimum number of rules required to sort the string in ascending order.

Fankoush is tired of sorting stuff for Malik, so he asked for your help again.

Input

The first line contains an integer $$$T$$$, the number of test cases $$$( 1 \le T \le 10^5 )$$$. For each test case:

  • The first line contains an integer $$$N$$$, the length of the string $$$( 2 \le N \le 10^5 )$$$.
  • The second line contains a string $$$S$$$ of length $$$N$$$ of lowercase letters.
It is guaranteed that the sum of $$$N$$$ over all test cases doesn't exceed $$$3.10^5$$$.
Output

Print the minimum number of rules. It can be proven that a solution always exists.

Example
Input
4
2
ab
2
ba
3
cba
3
cab
Output
0
1
1
2

L. Maze Chase
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Annoyed at sorting stuff for Sultan Malik, advisor Fankoush has stolen a powerful treasure and escaped into a deep maze. He will be taking some specific path that will lead him to a point of no return, where he will disappear without a trace.

The maze contains $$$N$$$ rooms. Each room is connected to one or multiple rooms by a passage. There are $$$M$$$ passages in the maze. Passage $$$i$$$ has length $$$w_i$$$.

The sultan's soldiers chase the thief, and each of them starts in some room in the maze. The soldiers know the exact path that Fankoush will take and the distances between the rooms.

Note the following:

  • The soldiers and the advisor Fankoush do not necessarily have the same speed.
  • All the soldiers have the same constant speed.
  • The time needed to traverse a path of length $$$l$$$ is $$$l / \text{speed}$$$.
  • If Fankoush reaches a room $$$x$$$ at time $$$t_1$$$, and one of the soldiers reaches the same room $$$x$$$ at time $$$t_2$$$, they will be able to catch him if $$$t_2 \leq t_1$$$.

The soldiers' mission is to catch Fankoush before he leaves the maze and escapes forever.

Your task is to help them find the number of the first room where they can intercept him. If it's impossible to catch him in time, you should return $$$-1$$$.

Input
  • The first line contains two integers $$$n$$$ and $$$m$$$ $$$(1 \leq n \leq 10^5, 0 \leq m \leq 10^5)$$$, representing the number of rooms and passages. Rooms are numbered $$$0$$$ to $$$n-1$$$.
  • Then, $$$m$$$ lines describing the passages of the graph, each $$$i$$$-th line contains three integers $$$u_i, v_i$$$ and $$$w_i$$$, representing an undirected edge between rooms $$$u_i$$$ and $$$v_i$$$ with weight $$$w_i$$$ $$$(distance)$$$ $$$(1 \leq w_i \leq 10^5)$$$.
  • The next line contains an integer $$$k$$$ $$$(1 \leq k \leq 10^5)$$$ followed by $$$k$$$ distinct rooms $$$(0$$$ to $$$n-1)$$$, representing Fankoush's path. The last one is the room before Fankoush leaves the maze forever.
  • The following line contains an integer $$$t$$$ $$$(1 \leq t \leq 10^5)$$$ followed by $$$t$$$ integers $$$(0$$$ to $$$n-1)$$$, representing each soldier's position.
  • The last line contains two integers $$$s_1$$$ and $$$s_2$$$ $$$(1 \leq s_1, s_2 \leq 10^5)$$$, representing Fankoush's speed and the soldiers' speed, respectively.

Note:

  • The graph may have disconnected components.
  • The path taken by Fankoush is guaranteed to exist in the graph.
  • It is guaranteed that there is a maximum of one edge between any two rooms.
Output

Print a single integer, the number of the first room in Fankoush's path where any soldier can intercept him, or $$$-1$$$ if no interception is possible before the last room.

Example
Input
6 7
0 2 1
0 5 3
1 2 2
1 3 2
1 4 2
1 5 2
2 3 2
3 3 1 5
2 0 2
11 10
Output
5