## COT - Count on a tree

You are given a tree with N nodes. The tree nodes are numbered from 1 to N. Each node has an integer weight.

We will ask you to perform the following operation:

• u v k : ask for the kth minimum weight on the path from node u to node v

### Input

In the first line there are two integers N and M. (N, M <= 100000)

In the second line there are N integers. The ith integer denotes the weight of the ith node.

In the next N-1 lines, each line contains two integers u v, which describes an edge (u, v).

In the next M lines, each line contains three integers u v k, which means an operation asking for the kth minimum weight on the path from node u to node v.

### Output

For each operation, print its result.

### Example

```Input:
8 5
105 2 9 3 8 5 7 7
1 2
1 3
1 4
3 5
3 6
3 7
4 82 5 12 5 22 5 32 5 47 8 2 ```
```Output:
2891057 ```

hide comments
 < Previous 1 2 3 Next > thedark: 2017-08-18 10:03:49 wtf n is not <= 1e5, wasted too much time, take limit of n 111111 to be on safe side.. Last edit: 2017-08-18 10:04:18 darkghostnj: 2017-07-26 22:05:16 the weights can be negative or bigger then 10^5 and that is why most people get WA on this problem ankit mathur: 2017-07-17 16:45:20 I found this Tc as the trickest one. 7 7 4 10 2 2 5 5 4 1 2 2 3 3 4 4 5 5 6 6 7 1 7 1 1 7 2 1 7 3 1 7 4 1 7 5 1 7 6 1 7 7 Output: 2 2 4 4 5 5 10 Also weight of nodes could be -ve also. and weight of nodes is greater than 10^5. kaushik_r: 2017-06-06 14:56:41 If we list the elements in the path from node 7 to node 8 in the given example, we'll get [7, 9, 105, 3, 7] . The 3rd minimum number in the list is 7 or 9? EDIT: Okay its 7 Last edit: 2017-06-06 15:50:58 r_ash: 2017-05-28 06:18:17 Last edit: 2017-06-03 13:42:35 californiagurl: 2017-05-23 15:24:46 I am getting WA. Is there any tricky test case? I used persistent segment tree, and even used long long. Last edit: 2017-05-23 15:27:13 chunkitlau: 2017-02-16 09:45:18 Last edit: 2017-02-16 09:49:50 Ravi kumar: 2016-10-26 23:25:44 n & m are greater than 10^5. cost me few wa :( vsp4: 2016-07-23 11:33:36 Very strict time limit. Had to use fast input output and then compress code :| :| due to source limit exceeding with fast input output -_- arjundabra: 2016-07-16 12:06:34 getting seg fault in c++ 5.1 but got ac in c++ 4.3.2.Why??

 Added by: Fotile Date: 2012-02-14 Time limit: 0.129s-0.516s Source limit: 6000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: ASM32-GCC ASM64 MAWK BC C-CLANG CPP14-CLANG CPP14 COBOL COFFEE D-DMD D-CLANG DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET Resource: Just for fun...