SOLVE

LATER

Don wants help

Problem

Editorial

Analytics

Don has a rooted tree, consisting of N vertexes. Each tree vertex has a unique index (integer from 1 to N), and also has a unique value associated to it.

The root of Don's tree has index 1.

Also Don has Q pairs of integers: X and Y. For each pair X, Y Don wants to know the Yth largest value in the path from root to Xth vertex.Let this value be **P**. Finally,Don asks you to calculate **S** such that

**S=f( (( P%100)+1)*2131669703889824641)** ,where f(x) is number of divisors of x.

Your task is to write a program that answer the queries asked by Don.

**INPUT**

First line contains an integer representing N the number of vertexes.
Next line contain n integers ,each representing the value(Ai) associated with each vertex from 1 to N.
Next N - 1 lines contain two integers U and V each, which means that vertex U and V are connected to each other.
Next line contains an integer Q, the number of Queries.
Next Q lines contain 2 integers X and Y each as described in the problem statement.
**All X will be distinct**

**OUTPUT**

For each query print the value of S in a new line

**If Yth largest value does not exist then print -1 only in a new line**.

**Constraints**

1<=N,Q<=100000

1<=Ai<=10^7

1<=X,Y<=10^6

**Author**-Akshay Vasandani

**Tester**-Akshay Vasandani

Time Limit:
1.0 sec(s)
for each input file.

Memory Limit:
256 MB

Source Limit:
1024 KB

Marking Scheme:
Marks are awarded when all the testcases pass.

Allowed Languages:
C,
C++,
Clojure,
C#,
D,
Erlang,
F#,
Go,
Groovy,
Haskell,
Java,
Java 8,
JavaScript(Rhino),
JavaScript(Node.js),
Lisp,
Lisp (SBCL),
Lua,
Objective-C,
OCaml,
Octave,
Pascal,
Perl,
PHP,
Python,
Python 3,
R(RScript),
Racket,
Ruby,
Rust,
Scala,
Scala 2.11.8,
Swift,
Visual Basic

Initializing Code Editor...

{"045677a": "/pagelets/recommended-problems/algorithm/don-wants-help/", "04566f9": "/pagelets/show-submission/algorithm/don-wants-help/", "0456740": "/pagelets/problem-author-tester/algorithm/don-wants-help/", "045675d": "/pagelets/problems-hint/algorithm/don-wants-help/", "0456720": "/pagelets/suggested-problems/algorithm/don-wants-help/"}

{}

realtime.hackerearth.com

80

0d29c5672a467f92ba12e1208fccdc445f3b9082

58a29e5cae2309f04b28

/realtime/pusher/auth/