• محدودیت زمان: ۰.۵ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت
• منبع: آزمون عملی دوره ۲۴ المپیاد کامپیوتر

---

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

با گرفتن زمان جایزه فرستادن‌ها و شخص‌فرستنده جایزه به سوالاتی شبیه سوال زیر پاسخ دهید:

• یک عضو جوان خانواده بلک تا یک روز مشخص حداکثر چند جایزه گرفته است؟

ورودی

در خط اول ورودی دو عدد n و q آمده اند که n تعداد اعضای خانواده بلک و q تعداد استفسارات (queryها) را نشان می‌دهد. در خط بعد n-1 عدد $p_2 ... p_n$ آمده است که شجره نامه خانواده بلک را مشخص می‌کند. فرض کنید اعضای خانواده به ترتیب سن با اعداد 1 تا n شماره‌گذاری شده‌اند. عدد $p_i$ شماره پدر(یا مادر) عضو شماره i را نشان‌ می‌دهد. رأس شماره 1 اولین عضو خانواده بلک است.

در هر یک از q خط بعد در هر خط یک استفسار آمده است. در اول هر خط یک کاراکتر آمده است که نوع استفسار را مشخص می‌کند. کاراکتر $ نشان دهنده‌ جایزه دادن و ? نشان دهنده پرسش است.

• در حالت $، در ادامه دو عدد v و t آمده است که نشان می‌دهد عضو شماره vام خانواده در روز t تصمیم می‌گیرد جایزه بخرد! دقت کنید که یک نفر ممکن است جوان باشد و برای خودش جایزه بگیرد.

• در حالت ?، در ادامه دو عدد v و t آمده است که نشان می‌دهد عضو شماره vآم خانواده از ابتدا تا روز t (شامل خود این روز) حداکثر چند جایزه گرفته است؟ تضمین می‌شود که این عضو یک بلک جوان است(فرزندی ندارد).

• استفسارات به ترتیب نانزولی برحسب زمان در ورودی ظاهر شده‌اند.

$$2 \leq n \leq 200\ 000$$ $$1 \le p_i \le i - 1 , 2 \le i \le n$$

$$ 1 \leq q \leq 200\ 000$$

$$ 1 \leq v \leq n $$

$$ 1 \leq t \leq 10^9$$

خروجی

در خروجی به ازای هر پرسش، جواب آن را در یک خط چاپ کنید.

زیرمسئله‌ها

زیرمسئله	نمره	محدودیت
۱	۱۵	$ n,q \le 2\ 000 $
۲	۱۰	$ n,q \le 50\ 000 $ و هر خانواده حداکثر یک بچه دارد. (گراف شجره‌نامه یک مسیر است.)
۳	۵۵	$ n,q \le 50\ 000 $
۴	۲۰	بدون محدودیت اضافی

مثال

ورودی نمونه

5 8
1 2 2 1
$ 2 1
? 3 3
$ 1 4
$ 2 4
? 3 4
? 3 5
? 3 6
? 5 6

خروجی نمونه

1
1
2
3
1

(۲۴امین دوره المپیاد کامپیوتر - آزمون سوم - ۱۳۹۳/۶/۶)