• محدودیت زمان: ۳ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

---

اگر به رفتار استف‌های کدکاپ ۳ در طول مسابقه دقت کرده‌باشید، درمی‌یابید که همه استفا عاشق مصطفی هستند.

کشور کوئرا از \(n\) شهر تشکیل شده است که این \(n\) شهر با \(n - 1\) جاده دوطرفه به هم متصل شده‌اند به طوری که از هر شهر می‌توان با طی کردن تعدادی جاده به شهر شماره ۱ رسید.

شهر شماره ۱ پایتخت کشور کوئراست و هرساله مجموعه مسابقات کدکاپ در این شهر برگزار می‌شود.

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

متاسفانه مسابقه کدکاپ با تعمیر جاده‌های کشور کوئرا توسط وزارت راه و ترابری، مصادف شده است و جاده‌ی شماره \(i\) که دو شهر \(x_i\) و \(y_i\) را به هم وصل می‌کند از روز \(l_i\) تا روز \(r_i\) در درست تعمیر است و امکان عبور از آن وجود ندارد. (یعنی اگر در روز \(k\)‌ ام به شهر \(x_i\) برسیم به طوری که \( l_i \le k \le r_i\)، باید تا روز \(r_i + 1\) صبر کنیم تا بتوانیم به شهر \(y_i\) برویم)

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

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

دقت کنید که تمامی استف‌ها در ثانیه‌ صفر از مبدا خود به سمت شهر ۱ راه می‌افتند.

ورودی

در یک خط عدد \(n\) که تعداد شهرهای کشور کوئراست به شما داده می‌شود.

در \(n - 1\) خط بعدی، درهر خط ۴ عدد \(x_i\) و \(y_i\) و \(l_i\) و \(r_i\) به شما داده می‌شود که به این معناست که جاده \(i\) ام شهر \(x_i\) و \(y_i\) را به هم وصل می‌کند و در زمان \(l_i\) تا \(r_i\) در دست تعمیر است.

\[ 2 \le n \le 500 \ 000 \] \[ 1 \le x_i , y_i \le n \] \[ 0 \le l_i \le r_i \le 500 \ 000 \]

تضمین می‌شود که با جاده‌های داده شده، از همه‌ی شهرها می‌توان به شهر شماره ۱ رسید.

خروجی

در \(n\) خط به ازای هر شهر یک عدد چاپ کنید که نشان می‌دهد استف‌های آن شهر در روز چندم به شهر ۱ ام می‌رسند.

مثال

ورودی نمونه ۱

2
1 2 1 2

خروجی نمونه ۱

0
0

ورودی نمونه ۲

3
1 2 3 4
2 3 0 2

خروجی نمونه ۲

0
0
5