Description

You're given a rooted tree, with N vertices number from 1...N. The root is vertex 1.

Each vertex has a weight. The weight of vertex i is W[i].

You're given Q queries. For query i, find out the K[i]-th max weight in subtree of vertex V[i].

Input

The first line contains two integer N and Q, which is the number of vertices and number of queries.

The second line contains N integer W[1], W[2], ..., W[N], which is the weight of vertices.

For the following N-1 lines, each line contains two integer A[i], B[i], which means there is an edge between vertex A[i] and B[i].

For the following Q lines, each line contains two interger V[i], Q[i]. Please find out the K[i]-th max weight in subtree of vertex V[i].

Constraints

• 2 <= N <= 10⁵
• 0 < W[i] <= 10⁹
• 1 <= A[i], B[i] <= N
• 1 <= Q <= 10⁵
• 1 <= V[i] <= N
• 1 <= K[i] <= 20
• The subtree rooted at vertex V[i] has K[i] or more vertices.

Output

Print Q lines, the i-th line is the answer of i-th query.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Daniel, Hank, and Noah are brothers. They were each given some binary tree of the same size which stores integers to traverse. They decide to traverse the binary tree with preorder, inorder and postorder respectively.

They want to know whether they are given the same binary tree or not.

Input

The first line of each input is t - The number of testcases.

Then the first line of each testcase contains n - The number of nodes of the binary tree.

Then followed by three lines.

pre - The preorder traversal of a tree.

in - The inorder traversal of a tree.

post - The postorder traversal of a tree.

Each data stored by the node i of the tree is a integer a_i. Each data in the traversal is seperated by an empty space.

Constrain

• 1 ≤ t ≤ 10
• 1 ≤ n ≤ 2 * 10⁵
• 1 ≤ a_i ≤ n
• In the same traversal, a_i ≠ a_j (if i ≠ j)
• It is promised that the nodes of each traversals are the same. Only the order of each nodes varies.

Output

For each testcase, if the three traversal is from the same tree, print "yes" in lowercase.

Otherwise, print "no" in lowercase.

Remember to print a ‘\n’ at the end of the output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Chyen's Burst Magic Adventurechyen has a strong liking for young magical beings known as "lolis", particularly those who possess the skill of Burst Magic. He has a special fondness for lolis who excel at using Burst Magic. To fulfill this interest, he sets out to teach Burst Magic to all N lolis in his collection. However, he encounters a dilemma: despite acquiring the knowledge of Burst Magic, the lolis lack opportunities to showcase their magical prowess, which leads to a growing sense of discouragement.

In response, chyen makes a decision. He plans to take a group of these lolis on a daring expedition to confront a formidable monster. This monster has a health level of M, and the lolis have the chance to unleash their Burst Magic upon it. Nevertheless, there are specific conditions to consider. Each loli possesses her own magical strength, denoted as m_i, and a measure of bravery, known as the courage value, represented by c_i. A loli can successfully employ Burst Magic to deal damage equal to her magical strength m_i, but only when the monster's health is equal to or less than her courage value c_i. Once a loli uses her Burst Magic, she becomes fatigued and cannot cast the spell again.

Your task is to determine the minimum number of lolis that chyen needs to take along on this adventure to successfully defeat the monster. If it is not possible to defeat the monster under any circumstances, please output -1.

Input

The first line contains two integers, N and M, representing the number of lolis and the monster's health respectively.

The subsequent N lines each provide two numbers, m_i and c_i, indicating the magical strength and courage value of the i-th loli.

1 ≤ M, N ≤ 106.

1 ≤ mi, ci ≤ 106, ∀i ∈ [1,N].

Output

Output the minimum number of lolis required to defeat the monster, or -1 if this task cannot be accomplished.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Maintain an integer ordered set S, which support the following operations:

• INS k: Insert k to S. If k is already in S, do nothing.
• DEL k: Delete the element in S with value k. If k is not in S, do nothing.
• IND k: Find the k-th smallest element in S, or report that the cardinality of S is smaller than k.

Input

The first line contains an integer q, representing the number of operations. Each of the following q lines is a single operation mentioned above.

Constraint

• 1 <= q <= 3 x 10⁵
• 1 <= k <= 10⁹ for every operation

Output

For each IND k operations, output the answer in each line. If the cardinality of S is smaller than k. output -1.

Sample Input  Download

Sample Output  Download

Tags

Discuss