Задається неспадний масив цілих чисел.

Напишіть програму, яка дає відповіді на запити:

• для заданого числа ~x_i~ знайти позицію його самого правого входження в заданий масив.

Input

Перший рядок містить два натуральних числа ~N~ та ~M~ (~1 \le N,M \le 10^5~).

Другий рядок містить ~N~ елементів масиву.

Наступні ~M~ рядків містять запити - числа ~x_i~. Елементи масиву цілі числа ~x_i~ по модулю не перевищують ~10^9~.

Output

Вивести в окремих рядках відповідь за завдання для кожного запиту. Якщо шуканий елемент не знайдено, то вивести 0.

Sample Input 1

3 3
1 3 5
1
5
7

Sample Output 1

1
3
0

Sample Input 2

4 2
1 1 3 3
1
3

Sample Output 2

2
4

У серіалі 'Американські боги' несподівано для нас існують боги і підвладні їм істоти. Божевільний Суїні - лепрекон і, як у кожного поважаючого себе лепрекона, у нього є горщик із золотими монетами, причому деякі з золотих монет є щасливими. У нього є ~n~ монет і для кожної щасливої відомо, що її номінал дорівнює (операція побітового виключного АБО - 'XOR') номіналів всіх монет, крім неї.

Суїні довірив вам свій горщик з монетами, але тепер у нього є ~q~ прохань до вас. Прохання бувають трьох типів:

1. Видалити з горщика монету номіналу ~x~, при цьому гарантується, що монета такої ваги присутня на даний момент.

2. Додати в горщик монету номіналу ~x~.

3. Знайти кількість щасливих монет.

Input

У першому рядку дано два цілих числа ~n~ і ~q~ (~1 \le n \le 5 \cdot 10^5~, ~1 \le q \le 5 \cdot 10^5~) - початкове число монет і кількість запитів.

У другому рядку дано ~n~ цілих чисел ~a_i~ (~1 \le a_i \le 2 \cdot 10^9~), де ~a_i~ - номінал ~i~-ї монети.

У наступних ~q~ рядках спочатку заданий тип запиту ~t~ (~1 \le t \le 3~) і, якщо запит першого або другого типу, потім задається номінал монети ~x~ (~1 \le x \le 2 \cdot 10^9~). Типи запитів і номінали монет - цілі числа.

Output

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

Sample Input 1

1 3
1
3
2 1
3

Sample Output 1

0
2

Notes

~i~-й біт побітового виключного АБО чисел ~a~ і ~b~ дорівнює 1, тоді і тільки тоді, коли ~i~-і біти чисел ~a~ і ~b~ різні.

Розглянемо «XOR» чисел 4 і 5, 4 = ~100_2~, а 5 = ~101_2~, тоді їх побітне виключне АБО дорівнює ~001_2~, тобто 1 в десятковій системі числення.

Розберемо приклад з умови. Спочатку є тільки одна монета, отже «XOR» всіх монет, крім неї, дорівнює 0, а отже щасливих монет немає. Потім додається ще одна монета вагою 1. «XOR» множини з однієї монети дорівнює її вазі, отже обидві монети щасливі.

Настя дуже любить серіали. Недавно у Netflix вийшов новий епізод «Чорного дзеркала». Але це не звичайний епізод, а інтерактивний. Всього в ньому є ~n~ моментів. Деякі моменти - розгалуження сюжету: для них існує вибір, в який момент піти наступним. У нашій версії гарантується, що до одного фіналу можна дістатися з початку тільки одним способом. Друзі Насті розповіли їй про ~k~ класних моментів. Оскільки Настя готується до олімпіади з інформатики, то вона не хоче витрачати багато часу на серіали, і тому вона вже взнала порядок моментів, а також перемотує вже переглянуті моменти.

Допоможіть Даші знайти мінімальну кількість моментів, які вона повинна подивитися, щоб дійти до всіх цікавих моментів.

Input

Перший рядок містить два цілих числа ~n~ і ~k~ (~2 \le n \le 5 \cdot 10^5~, ~1 \le k \le n~) - кількість можливих моментів і кількість моментів, які цікавлять Настю.

Другий рядок містить ~n~-1 ціле число ~a_i~ (~1 \le a_i \le i~), де ~a_i~ - момент, в якому треба зробити вибір, щоб дістатися до (~i~ + 1)-го моменту.

Останній рядок містить ~k~ цілих чисел - індекси потрібних Насті моментів. Індекси цікавих моментів різні.

Output

Виведіть одне число - мінімально можливу кількість переглянутих Дашею моментів.

Sample Input 1

3 2
1 2
2 3

Sample Output 1

3

Sample Input 2

5 2
1 1 1 4
1 2

Sample Output 2

2

Notes

У першому тесті Насті потрібно подивитися всі моменти, тому що вони всі цікаві для Насті.

У другому прикладі Настя може не відвідати 4 і 5 моменти, тому що Настя може дістатися до 2 моменту, минаючи тільки 1 і 2, а до 3 - тільки 1 і 3.

Напередодні виходу 8 сезону «Гри престолів» Степан переглянув всі попередні сезони і так захопився, що вирішив створити свою армію в боротьбі проти Короля Ночі. У «Грі престолів» є 7 королівств, але для ускладнення завдання він побудував свій всесвіт з ~n~ королівствами, де в кожному королівстві живе по ~m~ людей. Для краси і різноманітності він вирішив, що візьме по одній людині з кожного королівства і поставить їх в ряд так, щоб сума модулів різниці ростів сусідніх в ряду людей була мінімальна ~\sum_{i=1}^{n-1}|{a_i - a_{i+1}}|~.

Степан не зміг виконати це завдання, і тому просить вас допомогти йому.

Input

У першому рядку задано два натуральних числа ~n~ і ~m~ (~1 \le n \cdot m \le 10^5~) - кількість королівств і кількість жителів в кожному королівстві.

Наступні ~n~ рядків описують королівства. Кожен з цих рядків містить ~m~ натуральних чисел ~a_i~ (~1 \le a_i \le 10^9~), де ~a_i~ - ріст ~i~-ї людини в цьому королівстві.

Output

Виведіть послідовність чисел довжиною ~n~ - кожне число це ріст вибраної людини. Якщо відповідей декілька, то виведіть відповідь з мінімальною сумою всіх чисел.

Sample Input 1

3 2
2 2
6 7
99 1

Sample Output 1

1 2 6

Sample Input 2

2 2
9 9
6 3

Sample Output 2

6 9

Як ви вже знаєте, Танос заволодів усім камінням нескінченності. Тепер він перейшов до свого підступного плану. Спочатку у всесвіті було ~n~ героїв, пронумерованих від 1 до ~n~, деякі з них були живими, а деякі вже загинули. Клацання пальцями бере всіх персонажів на парних позиціях і або оживляє мертвих, або вбиває живих. Як багато хто з фанатів знає, Стен Лі є одним з богів всесвіту, і він вирішив погратися з Таносом і дав йому ~q~ запитів двох видів.

1. Клацнути пальцем на відрізку з ~l~ по ~r~. В ході цього запиту для всіх героїв з індексами виду ~l + 2k \le r~ виконується наступна операція: мертві оживають, а живі вмирають.

2. Знайти кількість все ще живих персонажів на відрізку з ~l~ по ~r~.

Input

У першому рядку дано два цілих числа ~n~ і ~m~ (~1 \le n, m \le 300000~) - кількість героїв і кількість запитів Стена Лі.

У наступному рядку дано ~n~ цілих чисел ~a_i~. ~a_i~ = 1, якщо персонаж живий, і 0, якщо мертвий.

У наступних ~m~ рядках дано три цілих числа ~t~, ~l~, і ~r~ (~1 \le t \le 2~, ~1 \le l \le r \le n~) - тип запиту і його ліва та права межі.

Output

Для кожного запиту другого типу виведіть одне число - кількість живих на відрізку з ~l~ по ~r~.

Sample Input 1

3 4
1 0 1
1 1 3
2 1 3
1 1 3
2 1 3

Sample Output 1

0
2