На далекой планете i1c5l обществом из n человек собран урожай в k апельсинов. Теперь стоит задача дележа урожая.
В этом обществе принята цветовая дифференциация штанов с элементами демократии, поэтому дележ урожая происходит следующим образом. В зависимости от цвета штанов каждый человек получает ранг от 1 до n. У всех людей штаны разного цвета. Далее человек с рангом 1 объявляет свое решение: кому и сколько апельсинов достанется. После этого все n человек голосуют «за» или «против». Если хотя бы половина людей проголосует «за», то решение объявляется принятым, в противном случае, человека, внесшего предложение, изгоняют из общества, а право объявить предложение переходит к человеку с рангом 2, и процедура повторяется.
При принятии решений и голосовании каждый человек действует оптимально для себя: пытается получить как можно больше апельсинов и при вариантах с равным количеством апельсинов стремится, чтобы в обществе осталось как можно меньше людей. Если человека изгоняют из общества, то считается, что он получил отрицательное число апельсинов. Из всех оптимальных решений человек может выбрать любое. Каждый человек знает, что остальные тоже действуют оптимально, руководствуясь теми же принципами.
Но один из этих людей обладает уникальными штанами-хамелеонами. Эти штаны могут по желанию хозяина принимать один из m цветов. Никакой из этих цветов не встречается у остальных людей.
Обладатель хамелеоновых штанов точно знает, какой ранг он получит для каждого цвета своих штанов. Ему осталось выяснить минимальное и максимальное количество апельсинов, которое он получит при каждом из цветов штанов.
В первой строке целые числа n, k и m (1 ≤ n, k ≤ 109, 1 ≤ m ≤ 105) — количество людей, апельсинов и возможных цветов штанов-хамелеонов соответственно.
Во второй строке m целых чисел a1, a2, ..., am (1 ≤ ai ≤ n), где ai — ранг обладателя хамелеоновых штанов при цвете i.
Для каждого ai на отдельной строке вывести минимальное и максимальное количество апельсинов, которые получит обладатель штанов цвета i или «-1 -1» (без кавычек), если его изгонят из общества.
2 10 2
1 2
10 10
0 0
3 1 2
1 3
0 0
1 1
В первом примере человек первого ранга забирает все апельсины себе и голосует «за».
Во втором примере человек с рангом 1 должен отдать апельсин человеку третьего ранга. Если первый заберет апельсин себе, то остальные проголосуют "против". Если первый отдаст апельсин второму, то второй все равно будет «против», т.к. знает, что, изгнав первого, он тоже получит апельсин, но людей в обществе останется меньше. Так как третий тоже будет «против», то этот вариант не подходит для первого.
