XOR Сума

Вам надано список із q (1 ≤ q ≤ 100000) команд.

Команда "insert n" додає число n до набору чисел (допускаються повтори чисел).

Команда "print" виводить XOR суму найбільших k (1 ≤ k ≤ q) елементів списку. Якщо в списку менше ніж k елементів, виводиться XOR сума всіх наявних елементів.

XOR сума набору чисел — це результат застосування операції XOR до всіх цих чисел. Операція XOR виконується над двома цілими числами за допомогою оператора ^ у багатьох мовах програмування або xor у Хаскелі (Паскалі).

Функція XOR має кілька важливих властивостей. Наприклад, якщо n ^ m = x, то n = x ^ m і m = x ^ n.

Вхідні дані

Перший рядок містить кількість тестів t (1 ≤ t ≤ 30). Кожен тест починається з рядка, що містить два цілі числа q та k (1 ≤ q, k ≤ 100000). Кожен із наступних q рядків містить одну команду.

Команди можуть бути двох типів:

insert n

або

print

n — невід'ємне число, менше 2^31.

Вихідні дані

Для кожної команди print виведіть XOR суму (не більше) k найбільших елементів у поточному списку. Пам'ятайте, що список очищується після обробки кожного тесту.

Приклади