Вычислительный сервис получает набор неотрицательных целых чисел. Каждое число приходит в собственной системе счисления, после чего сервис интерпретирует все записи, складывает соответствующие значения и выводит результат в заданной целевой системе счисления.

Поддерживаются системы счисления с основаниями от 2 до 36 включительно.

Для записи цифр используются символы:

• 0..9 для значений от 0 до 9,
• a..z для значений от 10 до 35.

Например, запись 1a в системе с основанием 16 означает число 26 в десятичной системе.

Требуется реализовать работу такого сервиса: по данным n записям чисел в различных системах счисления вычислить их сумму и вывести её в системе счисления с основанием target_base.

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

В первой строке заданы два целых числа n и target_base — количество чисел и основание целевой системы счисления.

В каждой из следующих n строк заданы два значения: base value, где:

• base — основание системы счисления данного числа,
• value — запись числа в этой системе счисления.

Гарантируется, что:

• все числа неотрицательны;
• длина каждой записи от 1 до 100 символов;
• все символы записи допустимы для соответствующего основания;
• запись числа либо равна 0, либо не содержит ведущих нулей.

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

Выведите запись суммы всех данных чисел в системе счисления с основанием target_base.

Если сумма равна нулю, выведите 0. Иначе выведите запись без ведущих нулей.

Ограничения

• 1 <= n <= 10^4
• 2 <= target_base <= 36
• для каждого числа: 2 <= base <= 36
• длина каждой строки value: от 1 до 100 символов

Примеры

Пример 1

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

1 2
10 0

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

0

Пример 2

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

3 16
2 1010
10 15
16 1a

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

3f71a