Simple And

তোমাকে N টি নোডের একটি ট্রি দেওয়া আছে । নোডগুল ১ থেকে N পর্যন্ত নম্বর করা । ট্রি এর রুট নোড হচ্ছে R । প্রত্যেক নোডে একটি করে নম্বর আছে । u নোডের নম্বরকে Xu দ্বারা প্রকাশ করা হয় ।

তোমাকে Q টি সহজ প্রশ্নের উত্তর দিতে হবে । প্রত্যেক প্রশ্নে ২ টি করে নম্বর (u, k) থাকবে । তোমাকে বলতে হবে u নোডের সাবট্রি তে k দূরত্বে যতগুলো নোড আছে তাদের Bitwise AND কত । যদি u নোডের সাবট্রি তে k দূরত্বে কোন নোড না থাকে তাহলে সে প্রশ্নের উত্তর হবে -১ ।

Input

ইনপুটের প্রথম লাইনে শুধুমাত্র একটি পূর্ণসংখ্যা T ( 1 ≤ T ≤ 5) থাকবে যা টেস্টকেসের সংখ্যা নির্দেশ করে।

প্রতিটি টেস্টকেসের প্রথম তিনটি নম্বর থাকবে N (1 ≤ N ≤ 105), Q (1 ≤ Q ≤ 105), R (1 ≤ R ≤ N) যা যথাক্রমে নির্দেশ করে ট্রি তে কতগুলো নোড আছে, কতগুলো প্রশ্ন করা হবে এবং ট্রি এর রুট নোড কোনটি ।

পরের লাইনে N টি নম্বর দেওয়া হবে । যা নির্দেশ করে Xu (0 ≤ Xu ≤ 109) এর মানগুলো ।

পরের N-1 লাইনে দুটি করে নম্বর (u, v) থাকবে । যা নির্দেশ করে ট্রিয়ের নোড u এবং নোড v এর মধ্যে একটি এজ আছে । এখানে (1 ≤ u, v ≤ N) ।

পরের Q লাইনে Q টি প্রশ্ন করা হবে । প্রত্যেক লাইনে দুটি করে নম্বর (u, k) থাকবে । যা একেকটি প্রশ্ন নির্দেশ করে । এখান (1 ≤ u ≤ N) এবং (0 ≤ k ≤ 105)।

বিশেষ দ্রষ্টব্যঃ ডেটা সেটটি অনেক বড়, ফাস্টার ইনপুট আউটপুট ব্যবহার করা উচিত।

Subtask Information

Subtask 1 (5 Points)
1 ≤ T ≤ 5
1 ≤ N ≤ 104
1 ≤ Q ≤ 104
0 ≤ Xu ≤ 109
0 ≤ k ≤ 105

Subtask 2 (5 Points)
1 ≤ T ≤ 5
1 ≤ N ≤ 105
1 ≤ Q ≤ 105
0 ≤ Xu ≤ 109
0 ≤ k ≤ 1

Subtask 3 (90 Points)
Orginal Constraints

Output

প্রত্যেক প্রশ্নের উত্তর গুলো নতুন লাইনে প্রিন্ট করতে হবে ।

Sample

Input	Output
1 8 6 1 3 23 5 6 15 11 14 10 1 2 2 4 4 8 3 5 3 6 3 7 3 2 2 2 3 1 4 2 1 2 1 3 1 1	10 10 -1 4 10 23
Here, 0-th child of node $2$ is ${2}$. 1st children of node $2$ are ${3, 4}$. 2nd children of node $2$ are ${5, 6, 7, 8}$. And there is no 3rd child of node $2$.

চিত্রে ২ নম্বর নোড থেকে ০ দূরত্বের নোড হচ্ছে {২} , ১ দূরতের নোড হচ্ছে {৩, 4} , ২ দূরত্বের নোড হচ্ছে {৫, ৬, ৭, ৮} । ২ নম্বর নোড থেকে ৩ দূরত্বের কোন নোড নেই ।