رستوران آقای خرچنگ دارای $n$ آشپز است که با اعداد ۱ تا $n$ شماره‌گذاری شده‌اند. هر آشپز $i$ (بجز شماره‌ی ۱ که سرآشپز است) یک آشپز ناظر مستقیم دارد که شماره‌ی آن $p_i$ است. آشپز شماره‌ی $i$ ناظر کلی آشپز شماره‌ی $j$ است، اگر و تنها اگر ناظر مستقیم او یا ناظر کلی آشپز $p_j$ باشد. همچنین حقوق آشپز شماره‌ی $i$ برابر $w_i$ است.

آقای خرچنگ به تازگی ورشکسته شده است برای همین قصد دارد تا نیروهای رستوران خود را تعدیل کند. او این کار را در دو مرحله انجام می‌دهد:

• در ابتدا او یکی از آشپزها‌ را به عنوان سرآشپز جدید انتخاب می‌کند و تمام کسانی که تحت نظارت کلی او نیستند را اخراج می‌کند.
• سپس تعداد ناصفری از آشپز‌های باقی‌مانده را نگه می‌دارد و بقیه‌ی آشپزها را اخراج می‌کند. از طرفی چون سلسله مراتب آشپز‌ها باید حفظ شود می‌بایستی تا به ازای هر آشپز باقی‌مانده (بجز سرآشپز جدید) ناظر مستقیم او نیز اخراج نشود.

آقای خرچنگ به شما اعتماد کرده تا بهترین تعدیل نیرو را انجام دهید، ولی شما از پلانکتون پول زیادی گرفته‌اید تا به ازای هر انتخاب سرآشپز در مرحله‌ی اول، انتخابی را در مرحله‌ی دوم انجام دهید که آقای خرچنگ بیشترین میانگین حقوق را پرداخت کند و این مقدار را خروجی دهید.

خط اول شامل عدد $n$ است که نشان‌دهنده‌ی تعداد آشپزهاست.

خط دوم شامل $n$ عدد است که با فاصله از هم جدا شده‌اند و عدد $i$اُم نشان‌دهنده‌ی مقدار $w_i$ است.

خط سوم شامل $n-1$ عدد است که با فاصله از هم جدا شده‌اند و عدد $i$اُم نشان‌دهنده‌ی $p_{i+1}$ است.

خروجی شامل $n$ خط است. در خط $i$اُم خروجی اگر مقدار جواب به ازای انتخاب آشپز $i$ به عنوان سرآشپز جدید برابر با $ans_i$ باشد، باید به ترتیب دو عدد $P_i$ و $Q_i$ را خروجی دهید که $ans_i = \frac{P_i}{Q_i}$ و $\gcd(P_i,Q_i) = 1$ است. به ازای هر $i$ که $ans_i = 0$ بود، مقادیر $P_i=0$ و $Q_i=1$ را درنظر بگیرید.

• زیرمسئله اول (۳ نمره): $n \leq 17$
• زیرمسئله دوم (۱۱ نمره): $n \leq 5000$
• زیرمسئله سوم (۱۰ نمره): $p_i = \lfloor \frac{i}{2} \rfloor$
• زیرمسئله چهارم (۳۲ نمره): $p_i = i-1$
• زیرمسئله پنجم (۴۴ نمره): بدون محدودیت اضافی

• $1 \leq n \leq 3 \times 10^5$
• $1 \leq p_i < i$
• $0 \leq w_i \leq 10^{12}$

به ازای هر زیرمسئله، اگر خروجی شما برای آشپز شماره ۱ (همان سرآشپز اولیه) درست باشد ۲۰٪ نمره‌ی زیرمسئله را دریافت می‌کنید.

• به ازای انتخاب آشپز شماره ۱ به عنوان سرآشپز، مجموعه آشپز‌های $\{1, 2, 4\}$ را نگه می‌داریم.
• به ازای انتخاب آشپز شماره ۲ به عنوان سرآشپز، مجموعه آشپزهای $\{2, 4\}$ را نگه می‌داریم.
• به ازای انتخاب سایر آشپزها به عنوان سرآشپز، تنها خود آن فرد را نگه می‌داریم.