Dana jest drzewo o $n$ wierzchołkach, spełniające następujące właściwości:

1. Wszystkie liście znajdują się na tej samej głębokości.
2. Wierzchołki są ponumerowane zgodnie z kolejnością BFS, zgodnie z następującą konstrukcją:
   1. Korzeń ma numer 1 i jest dodawany do kolejki.
   2. W każdym kroku pobieramy wierzchołek z początku kolejki, a jego dzieciom przypisujemy kolejne nieużyte numery i dodajemy je do kolejki w kolejności przypisywania numerów.

Każdy wierzchołek ma przypisaną wagę, początkowo równą 0.

Dostępne są dwa rodzaje operacji:

• Operacja 1: Dodaj $y$ do wagi każdego wierzchołka w poddrzewie wierzchołka $x$.
• Operacja 2: Wykonaj rotację wag wierzchołków, przenosząc wagę wierzchołka $i$ do wierzchołka $(i \bmod n) + 1$.

Oblicz wagi wszystkich wierzchołków po $q$ operacjach. Aby uniknąć zbyt dużego wyjścia, wypisz sumę XOR wag wszystkich wierzchołków.

Wejście

W pierwszej linii znajdują się dwie liczby $n$ oraz $q$, oznaczające odpowiednio liczbę wierzchołków w drzewie oraz liczbę operacji.

W kolejnej linii znajduje się $n-1$ liczb, gdzie $i$-ta liczba $fa[i+1]$ oznacza ojca wierzchołka $i+1$ (zgodnie z właściwościami BFS, dla $i \leq j$ zachodzi $fa[i] \leq fa[j]$).

Następnie podano $q$ linii opisujących operacje. Jeśli linia zaczyna się od 1 x y, oznacza to operację typu 1: dodanie $y$ do wierzchołków w poddrzewie $x$. Jeśli linia zaczyna się od 2, oznacza to operację typu 2: wykonanie rotacji.

Wyjście

Wypisz jedną liczbę, będącą sumą XOR wag wszystkich wierzchołków.

Przykład

Wejście 1

6 10
1 1 2 3 3
1 3 1
1 2 2
2
1 4 3
1 5 4
2
2
1 1 5
2
1 6 6

Wyjście 1

10

Uwagi

Rzeczywiste wagi wynoszą:

9 11 6 6 5 13

Suma XOR wynosi 10.

Ograniczenia

Dla 100% danych: $n, Q \leq 100\,000$, $y \leq 10\,000$.