U gradu Jenotu, punom rakuna, traje festival hrane. Glavni rakun želi okupiti sve svoje sljedbenike i želi da svaki sa sobom ponese svoju omiljenu hranu. Kao i u svakom gradu, svaki rakun osim rakuna broj jedan ima svoga nadređenog. Svaki rakun će svome nadređenom donijeti svoju hranu na pregled. Kada se okupe svi podređeni i pokažu nadređenom svoju hranu, svi zajedno idu do nadređenog nadređenomu i tako redom dok svi ne dođu do glavnoga.

Sada je šefova pametna pomoćnica Zoe primijetila da mnogo rakuna ima istu omiljenu hranu i želi da bude malo raznovrsnije. Kako bi to učinila moli vas da joj pomognete sa dvije vrste upita:

1. Izračunajte koliko različitih vrsta hrane imaju rakuni podređeni rakunu \(x\), uključujući njega.
2. Promjenite vrstu hrane koju rakun \(x\) nosi na \(y\).

U početku poznati su vam broj rakuna \(n\), nadređeni od svakog osim prvog rakuna rakuna \(p_i\), hranu koju \(i\)-ti rakun trenutno nosi \(a_i\) te \(q\) upita iz teksta oblika \(1\) \(x\) ili \(2\) \(x\) \(y\).

Ulazni podatci:

U prvome retku nalaze se prirodni brojevi \(n\) i \(q\) (\(1 \leq n, q \leq 10^5\)), broj rakuna te broj upita od Zoe.

U drugome retku nalazi se \(n-1\) brojeva od kojih \(i\)-ti predstavlja nadređenog od rakuna označenog broja \(i+1\).

U trećemu retku nalazi se \(n\) prirodnih brojeva \(a_i\) (\(1 \leq a_i \leq 10^5\)) od kojih \(i\)-ti predstavlja vrstu hrane koju će \(i\)-ti rakun ponijeti.

U idućih \(q\) redova nalaze se dvije vrste upita iz zadatka, \(1\) \(x\) ili \(2\) \(x\) \(y\).

Izlazni podatci:

Ispišite traženi broj za upite vrste 1.

Podzadatci

Ulaz primjera 1

5 5
1 2 3 3
1 2 3 4 5
1 3
2 4 3
1 3
2 5 3
1 3

Izlaz primjera 1

3
2
1

Pojašnjenje prvog probnog primjera

U prvom query ispod rakuna označenog brojem 3 su rakuni 4 i 5. U početku imaju brojeve 3, 4, i 5. Nakon prve promjene imati će hrane brojeva 3, 3, 5. Te nakon zadnje promjene svi troje će imati hranu boje 3, 3, 3.