Вам дан список из 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 - неотрицательное число, меньшее 231.

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

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