У земљи Бајтовији налази се \(N\) насеља, означених различитим целим бројевима од \(1\) до \(N\). Постоји \(N-1\) путева између неких насеља, тако да је могуће стићи од било ког насеља до било ког другог користећи те путеве (тј. Бајтовија је облика стабла). Растојање два насеља је дужина најкраћег пута између та два насеља.

У бази података Јавног Комуналног Предузећа Путеви Бајтовије сва насеља налазе се поређано неким редоследом \(p_i\) (означава да је \(i\)-то насеље у реду насеље \(p_i\)).

У једном тренутку кренуле су да се дешавају чудне ствари у два облика:

• \(1\) \(a\) \(b\), администратори база података заменили су у редоследу \(p_a\) и \(p_b\).
• \(2\) \(l\) \(r\) \(x\), хакери су упали у систем и уцењују администраторе. Траже им одговор на питање: колико је далеко насеље \(x\) од најдаљег од насеља \(p_l, p_{l+1}, \ldots, p_r\).

Администратори база података Јавног Комуналног Предузећа Путеви Бајтовије вас моле за помоћ да одговорите на питања хакера.

Опис улаза

У првом реду стандардног улаза налази се природан број \(N\) - број насеља. У другом реду налази се \(N\) целих бројева, редослед насеља на списку. Наредних \(N-1\) редова садрже два броја \(u\) и \(v\), означавајући да постоји пут између насеља нумерисаних \(u\) и \(v\).

Наредни ред садржи природни број \(Q\), број догађаја. Свака од наредних \(Q\) линија садржи или \(1\) \(a\) \(b\) - означавајући догађај првог типа - или \(2\) \(l\) \(r\) \(x\) - означавајући догађај другог типа.

Опис излаза

За сваки догађај другог типа потребно је исписати у засебном реду стандардног излаза одговор на питање уцењивача.

Пример

Улаз

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

Излаз

2
2
3

Објашњења примера

Први догађај: најдаље насеље од насеља \(5\) на датом интервалу је насеље \(1\), на растојању \(2\).

Други догађај: замена позиције насеља \(1\) и \(3\).

Трећи догађај: најдаље насеље од насеља \(5\) на датом интервалу је насеље \(3\), на растојању \(2\).

Четврти догађај: замена позиције насеља \(4\) и \(2\).

Пети догађај: најдаље насеље од насеља \(5\) на датом интервалу је насеље \(4\), на растојању \(3\).

Ограничења

• \(1 \leq N, Q \leq 80.000\)
• \(1 \leq p_i \leq N\) и \(p_i \neq p_j\) за \(i \neq j\)
• \(1 \leq a, b, x, u, v \leq N\) и \(a \neq b\)
• \(1 \leq l \leq r \leq N\)

Тест примери су подељени у 5 дисјунктних група:

• У тест примерима вредним \(10\) поена: \(N, Q \leq 4000\).
• У тест примерима вредним \(15\) поена: Свако насеље је суседно са највише два друга насеља.
• У тест примерима вредним \(25\) поена: У сваком догађају важиће \(x = 1\) и \(p_a, p_b \neq 1\)
  
• У тест примерима вредним \(25\) поена: Нема догађаја облика \(1\).
• У тест примерима вредним \(25\) поена: Без додатних ограничења.