Water in a Tree

একটি Tree আছে $N$ সংখ্যক নোড এবং $N-1$ সংখ্যক এজ সমৃদ্ধ। $i^{th}$ নোড এ $S_i$ লিটার পানি আছে এবং পানির তাপমাত্রা $T_i$ ডিগ্রী।
প্রতিটি নোড এর পানির তাপমাত্রা বদল হয়না যতক্ষণ পর্যন্ত অন্য তাপমাত্রার পানির সাথে না মেশানো হয়।

আপনাকে $Q$ সংখ্যক অপারেশন চালাতে হবে ট্রি এর উপর। অপারেশন হবে মোট দুই ধরণের।

$Type 1:$ আপনাকে একটি পাথ দেওয়া থাকবে নোড $U$ থেকে নোড $V$ পর্যন্ত। আমরা যদি নোড $U$ থেকে নোড $V$ পর্যন্ত সবগুলো নোড এর পানি একসাথে মিশাই, তাহলে ওই মেশানো পানির তাপমাত্রা কত ডিগ্রী হবে? আর মোট পানির পরিমাণ কতো লিটার হবে? ট্রি এর কোন value এই ধরণের কুয়েরি দ্বারা বদলাবে না। আমরা যখন নোড $a$ আর নোড $b$ এর পানি মিশাবো, তাপমাত্রা নির্ধারণে নিচের নিয়মটি মেনে চলবেঃ

$T_a × S_a + T_b × S_b = T_c × (S_a+S_b)$.

এখানে $T_a$ আর $T_b$ হচ্ছে পর্যায়ক্রমে নোড a এবং নোড b এর পানির তাপমাত্রা। $S_a$ এবং $S_b$ হচ্ছে পর্যায়ক্রমে নোড a এবং নোড b এর পানির পরিমাণ। $T_c$ হচ্ছে নতুন তাপমাত্রা যা দুই নোড এর পানি মেশানোর পর পাওয়া যাবে।

$Type$$2:$ নোড $U$ এর পানির তাপমাত্রা আর পানির পরিমাণ পরিবর্তন করুন।

Input

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

পরবর্তী মোট $N-1$ লাইনের প্রতিটি লাইনে দুটি করে ইন্টিজার থাকবে $U$ আর $V$$(1 \leq U, V \leq N, U\neq V)$ যা দিয়ে বুঝার এখানে একটি এজ রয়েছে নোড $U$ আর নোড $V$এর মাঝে।

পরবর্তী $N$ লাইনের প্রতিটি $i$ এর জন্য যা $1$ থেকে শুরু করে $N$ পর্যন্ত নির্দেশ করে, $i^{th}$ লাইনের দুটি integers $T_i$ আর $S_i$ $(1\leq T_i, S_i \leq 10^3)$থাকবে। $T_i$ হচ্ছে $i^{th}$নোড এর পানির তাপমাত্রা আর $S_i$ হচ্ছে $i^{th}$ নোড এর পানির পরিমাণ যার একক লিটার।

পরবর্তী Q লাইন একটি করে কুয়েরি নির্দেশ করে।

$Type$ $1:$ 1 $U$ $V$ $(1 \leq U, V \leq N)$.
$Type$ $2:$ 2 $i$ $T_i$ $S_i$ $(1 \leq T_i, S_i \leq 10^3)$ এখানে $T_i$ এবং $S_i$ হচ্ছে integer numbers যা নোড $i$ এর পানির নতুন তাপমাত্রা এবং পরিমাণ নির্দেশ করে।

প্রতিটি দ্বিতীয় ধরণের কুয়েরির জন্য, $i^{th}$ নোড এর পানির তাপমাত্রা বদল করুন $T_i$ দিয়ে আর পানির পরিমাণ বদল করুন $S_i$ লিটার দিয়ে।

For 40 Points: Every constraint is less than or equal to $10^3$.
For 100 Points: Original constraints.

Output

প্রতিটি প্রথম ধরণের কুয়েরি এর জন্য দুটি বাস্তব সংখ্যা ${X }$ আর $Y$প্রিন্ট করুন। $X$ হচ্ছে গড় তাপমাত্রা আর $Y$ হচ্ছে মোট পানির পরিমাণ যদি আমরা নোড $U$ থেকে নোড $V$ তে যাওয়ার পাথ এর সব নোড এর পানি একত্রে মিশাই।

আপনার উত্তর সঠিক বলে গণ্য করা হবে যদি এর relative or absolute error $10^{-4}$ এর বেশি না হয়।

Sample

Input	Output
5 4 1 2 2 3 2 4 1 5 30 2 80 1 70 2 50 3 100 1 1 2 5 1 5 3 2 2 70 2 1 5 3	60.00000 4.00000 63.33333 6.00000 62.85714 7.00000