Задача A. Турникеты в метро ≡

Условие

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

При каждом проходе через турникет высвечивается, сколько еще дней карта может быть использована (включая текущий день). Но, к сожалению, табло, на котором это количество дней отображается, может показывать только однозначные и двузначные числа. Если же в отображаемом числе хотя бы три цифры, на табло покажется число 99. Например, если на карте осталось 5 дней, то на турникете покажется число 5, если 12 дней, то число 12, а если 123 дня, то на турникете покажется число 99. Если на карте остается 0 дней, она становится неактивной и по ней больше нельзя проходить через турникет.

Сейчас у Васи на карте осталось a дней, а у Пети — b. Они каждый день ездят на метро и каждый день смотрят на числа, которые отображаются на турникете. И им стало интересно: через сколько дней в первый раз число на турникете у одного из них будет ровно в k раз больше, чем число на турникете у другого. Помогите друзьям выяснить ответ на этот вопрос.

Формат входного файла

Первая строка входных данных содержит одно число t — количество тестов. Следующие t строк содержат по тесту каждая. Каждый тест задается тремя целыми числами: a, b, k — количество оставшихся дней на карточках у Васи и Пети и требуемое отношение.

Формат выходного файла

Для каждого набора данных выведите единственное число: через сколько дней у одного из друзей на турникете будет показано в k раз больше поездок, чем у другого. Если такого не произойдет до того дня, когда у одного из друзей карта станет неактивной, выведите -1.

Ограничения

1 ≤ t ≤ 100000

1 ≤ a, b ≤ 2·10⁹

1 ≤ k ≤ 100

Примеры тестов

5
2 1 2
100 99 2
17 13 10
3 3 1
1 1 2

0
98
-1
0
-1

Задача B. cd-DOS ≡

Условие

В операционной системе cd-DOS поддерживается иерархическая структура каталогов, аналогичная MS-DOS. Полный путь к каталогу здесь записывается как строка, содержащая последовательность имен каталогов, разделенных знаком "\", имени диска в пути не указывается. Например, "ff\sample\path". В отличие от MS-DOS, cd-DOS понимает только упрощенный вариант команды cd (Change Directory - смена текущего каталога). При помощи этой команды в cd-DOS можно перейти только на один уровень вверх или вниз по иерархии каталогов (например, команды "cd .." или "cd MyDir" разрешены, но "cd ..\..\otherdir" или "cd some\moredir" запрещены).

Требуется по данным полным путям к двум каталогам определить минимальное количество команд cd, необходимых для перехода из одного каталога в другой.

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

a\b\c	
a\c\d

4

same
same\a

1

Задача C. Магические карточки ≡

Условие

Гриша и Дима увлекаются игрой "Магические карточки". В колоде для игры содержатся карточки с написанными на них натуральными числами. В каждой игре участникам выдается по n карточек. Затем у каждого из участников случайным образом выбирается по l карточек. Выигрывает тот, сумма чисел на выбранных карточках которого больше. Если суммы равны, то объявляется ничья.

Гриша очень не любит проигрывать, поэтому он даже подглядел карточки Димы. Теперь он хочет узнать, верно ли, что он гарантированно выигрывает, вне зависимости от того, какие карточки будут случайным образом выбраны у него и у Димы. Ничья Гришу не устраивает, он хочет именно выиграть.

Ваша задача состоит в том, чтобы по наборам карточек и известному числу l определить, верно ли, что Гриша в любом случае выиграет игру.

Формат входного файла

Первая строка содержит целое положительное число t —— число тестовых примеров во входных данных. Далее следуют описания тестовых примеров.

Каждый тестовый пример описывается тремя строками. Первая строка содержит два целых положительных числа n и l —— количество карточек у игроков и количество карточек, которые выбираются случайным образом. Вторая строка содержит n целых положительных чисел a₁, a₂, ..., a_n —— числа, написанные на карточках Гриши. Третья строка содержит n целых положительных чисел b₁, b₂, ..., b_n —— числа, написанные на карточках Димы.

Гарантируется, что сумма значений n по всем тестовым примерам не превышает 10000.

Формат выходного файла

Выведите t строк. Для каждого тестового примера выведите "YES", если Гриша выиграет при любом случайном выборе карточек, либо "NO" в противном случае.

Ограничения

1 ≤ l ≤ n ≤ 100

0 ≤ a_i ≤ 1000

0 ≤ b_i ≤ 1000

Примеры тестов

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

NO
YES

Задача D. Тест: задания типа ЕГЭ, часть 1 ≡

Условие

Формат выходного файла

В качестве решения принимается текстовый файл, содержащий по одному числу в строке — ответы на каждый из вопросов. При отправке файла следует выбрать в тестирующей системе среду разработки "Answer text". Если вы не знаете ответа на какой-то из вопросов, укажите вместо ответа число 0.

Задача E. Тест: задания типа ЕГЭ, часть 2 ≡

Условие

Формат выходного файла

В качестве решения принимается текстовый файл, содержащий по одному числу в строке — ответы на каждый из вопросов. При отправке файла следует выбрать в тестирующей системе среду разработки "Answer text". Если вы не знаете ответа на какой-то из вопросов, укажите вместо ответа число 0.

Задача F. Тест: задания типа ЕГЭ, часть 3 ≡

Условие

Формат выходного файла

В качестве решения принимается текстовый файл, содержащий по одному числу в строке — ответы на каждый из вопросов. При отправке файла следует выбрать в тестирующей системе среду разработки "Answer text". Если вы не знаете ответа на какой-то из вопросов, укажите вместо ответа число 0.