Дано дерево с $n$ вершинами, обладающее следующими свойствами:

1. Глубина всех листьев одинакова.
2. Вершины пронумерованы в порядке BFS (поиск в ширину), процесс нумерации описан ниже:
   1. Корневая вершина имеет номер 1, она добавляется в очередь.
   2. На каждом шаге извлекается голова очереди, а её потомкам последовательно присваиваются следующие неиспользованные номера, после чего они добавляются в очередь в порядке возрастания номеров.

Каждая вершина имеет вес, изначально равный 0.

Доступны два типа операций:

• Операция 1: прибавить $y$ к весу каждой вершины в поддереве вершины $x$.
• Операция 2: выполнить циклическую перестановку весов вершин, переместив вес вершины $i$ в вершину $(i \bmod n) + 1$.

Найдите веса всех вершин после $q$ операций. Чтобы избежать вывода слишком большого объема данных, выведите побитовое исключающее ИЛИ (XOR) всех полученных весов.

Входные данные

Первая строка содержит два числа $n$ и $q$ — количество вершин в дереве и количество операций соответственно.

Следующая строка содержит $n-1$ число, где $i$-е число $fa[i+1]$ обозначает родителя вершины $i+1$ (согласно свойствам BFS, при $i \leq j$ выполняется $fa[i] \leq fa[j]$).

Далее следуют $q$ строк, описывающих операции. Если строка начинается с 1 x y, это означает операцию 1: прибавить $y$ к весам вершин в поддереве $x$. Если строка содержит 2, это означает операцию 2: выполнить циклическую перестановку.

Выходные данные

Выведите одно число — XOR-сумму весов всех вершин.

Примеры

Пример 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

Выходные данные 1

10

Примечание 1

Фактические веса вершин:

9 11 6 6 5 13

Их XOR-сумма равна 10.

Ограничения

Для всех тестов: $n, Q \leq 100\,000$, $y \leq 10\,000$.