Yet Another Xinversion

তোমাকে একটি ট্রি দেয়া আছে যার রুট $1$। প্রত্যেক নোডের একটি করে ভ্যালু আছে, ধরা যাক $C_i$ । তোমাকে $Q$ টি অপারেশন করতে হবে। অপারেশন গুলো দুই ধরনের হতে পারে।

• তোমাকে $u, val$ দেয়া হবে, $C_u = val$ করতে হবে।
• তোমাকে $u$ দেয়া হবে, তোমাকে বলতে হবে $u$ এর Xinversion কতো।

Xinversion অনেকটা অ্যারের ইনভার্শনের মতো। যদি একটা নোড $u$ এর সাবট্রি তে $k$ টা নোড থাকে যাদের ভ্যালু $u$ এর ভ্যালুর থেকে বেশি তাহলে ওই নোডের Xinversion হবে $k$ ।

Input

প্রথম লাইনে দুটি পূর্নসংখ্যা $N(1 \leq N \leq 10^5), Q(1 \leq Q \leq 10^5)$ দেয়া হবে যেগুলো যথাক্রমে মোট নোডের সংখ্যা এবং মোট অপারেশনের সংখ্যা প্রকাশ করে।

পরবর্তী লাইনে N টি সংখ্যা থাকবে যেগুলে যথাক্রমে $C_1. C_2. C_3......C_N$ ।

পরবর্তী $N-1$ লাইনে দুটি করে সংখ্যা $x, y$ থাকবে যার মানে $u$ এবং $v$ একটি এজ দিয়ে যুক্ত।

পরবর্তী $Q$ লাইনে একটি করে অপারেশন থাকবে। অপারেশন নিচের দুই ধরনের হতে পারে:

• 1 x val
• 2 x

Output

প্রত্যেক কুয়েরির জন্য তোমাকে $x$ এর Xinversion প্রিন্ট করতে হবে।

Sample

Input	Output
5 5 1 2 3 4 5 1 2 2 3 2 4 3 5 2 1 2 2 1 3 1 1 4 1 2 1	4 3 2