آقای تست (mr.toast) بعد از قراردادش با فیسبوک به ثروت فراوانی رسید. علاقه‌ی آقای تست به بازی کامپیوتری valorant باعث شد به دنیای مسابقات بازی‌های کامپیوتری روی بیاورد. از آنجایی که آقای تست بسیار ثروتمند است و دوست دارد همیشه تیمی در مسابقات داشته باشد، تصمیم به خرید یک تیم می‌کند. ولی از آنجایی که آقای تست از باختن متنفر است، بعد از باخت تیمش، مجبور است تیم برنده را نیز بخرد، و ادامه‌ی مسابقات را با آن تیم ادامه بدهد.

در مسابقات بازی‌های کامپیوتری valorant هر یک از $n$ تیم شرکت‌کننده دارای قدرتی برابر با $p_i$ و قیمتی برابر با $c_i$ می‌باشد. همچنین مسابقات به صورت حذفی برگزار می‌شود که می‌توان گراف آن را به شکل یک درخت دودویی نشان داد که $n$ تیم شرکت‌کننده متناظر برگ‌های درخت بوده و هر راس دیگر نشان‌دهنده‌ی مسابقه بین دو فرزندش است که برنده‌ی آن مسابقه به این راس صعود می‌کند و تیم دیگر حذف می‌شود. توجه کنید که این درخت لزوما یک درخت دودویی کامل نیست.

در یک بازی بین دو تیم $i$ و $j$ احتمال برد تیم $i$ برابر با $\frac{p_i}{p_i + p_j}$ است. آقای تست به ازای هر $i$ می‌خواهد بداند که اگر با خریدن تیم $i$ ام شروع کند، امید ریاضی هزینه‌ای که تا آخر مسابقات پرداخت می‌کند چقدر است.

می‌توان نشان داد امید ریاضی واقعه‌ی خواسته شده را می‌توان به صورت $\frac{P}{Q}$ نوشت که $P$ و $Q$ نسبت به هم اول‌اند. شما باید مقدار $P \cdot Q^{-1} \mod 998244353$ را محاسبه کنید و در خروجی آن را چاپ کنید.

در خط اول ورودی عدد طبیعی $n$ تعداد برگ‌های درخت می‌آید.

در خط دوم ورودی $p_1, p_2, ..., p_n$ قدرت تیم‌ها می‌آید.

در خط سوم ورودی $c_1, c_2, ..., c_n$ قیمت تیم‌ها می‌آید.

در هر یک از $n - 1$ خط بعدی در خط $i$ ام، دو عدد $v_i$ و $u_i$ به ترتیب می‌آیند که نشان‌دهنده‌ی مسابقه‌ای بین نماینده‌های $v_i$ و $u_i$ است که برنده‌شان به راس $n + i$ صعود می‌کند. در واقع فرزندان راس $n + i$ هستند.

تنها خط خروجی شامل $n$ عدد است که عدد $i$ ام نشان‌دهنده‌ی امید ریاضی پولی است که آقای تست در صورت شروع با تیم $i$ ام باید پرداخت کند. (در صورت شروع با تیم $i$ ام، این تیم حتما خریداری می‌شود.)

• زیرمسئله اول (۱۵ نمره): $n \leq 500$
• زیرمسئله دوم (۱۵ نمره): $p_i = 1$
• زیرمسئله سوم (۷۰ نمره): بدون محدودیت اضافی

• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۵۱۲ مگابایت
• $1 \leq n \leq 3000$
• $1 \leq v_i, u_i < n + i$
• $1 \leq p_i \leq 10^6$
• $1 \leq c_i \leq 10^9$

• سوال قبل
• سوال بعد