Без легенди

Вам дано дерево з $n$ вершинами, де коренем є вершина $1$.

Вважатимемо, що безпосереднім батьком вершини $i$ є $a_i(1\le a_i<i)$ для всіх $(2\le i\le n)$.

Необхідно виконати $q$ запитів двох типів:

• Дано три цілі числа $l,r$ і $x(2\le l\le r\le n,1\le x\le 10^5)$. Потрібно замінити $a_i$ на $max(a_i-x,1)$ для всіх $i$, де $l\le i\le r$.

• Дано два цілі числа $u,v(1\le u,v\le n)$. Потрібно знайти LCA (найменшого спільного предка) вершин $u$ і $v$.

Вхідні дані

Перший рядок містить два цілі числа $n$ і $q(2\le n,q\le 10^5)$ — кількість вершин і кількість запитів відповідно.

Другий рядок містить $n-1$ цілих чисел $a_2,a_3,...,a_n(1\le a_i<i)$, де $a_i$ є батьком вершини $i$.

Наступні $q$ рядків містять запити. Для кожного запиту першим числом у рядку є $t(t=1$ або $2)$ — тип запиту.

Якщо $t=1$, це запит першого типу. Далі йдуть три цілі числа: $l,r,x(2\le l\le r\le n,1\le x\le 10^5)$, що означає, що потрібно замінити $a_i$ на $max(a_i-x,1)$ для всіх $i$, де $l\le i\le r$.

Якщо $t=2$, це запит другого типу. Далі йдуть два цілі числа: $u$ і $v(1\le u,v\le n)$, і потрібно знайти LCA для $u$ і $v$.

Гарантується, що є принаймні один запит другого типу.

Вихідні дані

Для кожного запиту другого типу виведіть відповідь у новому рядку.

Приклади