Queue Data Structure
Древние династии
История Татаро-монгольского ханства богата на правителей. Каждый из n правителей принадлежал к одной из двух династий, причём власть часто переходила от одной династии к другой. Каждое восхождение правителя на престол отмечалось праздником, проводимым 26 марта. В летописях зафиксированы годы проведения этих праздников, причем известно, что правители первой династии устраивали для народа праздник кумыса, а второй - праздник мёда.
На конференции по истории Татаро-монгольского ханства каждый из s учёных предложил свою версию толкования летописи. А именно, i-й историк утверждал, что от каждого праздника кумыса до следующего праздника кумыса проходило не менее kl[i] лет, но не более kr[i] лет, в то время как от каждого праздника мёда до следующего праздника мёда проходило не менее ml[i] лет, но не более mr[i] лет.
Каждой предложенной версии может соответствовать несколько распределений правителей по династиям. Ученые договорились считать показателем сомнительности распределения число переходов власти к представителю той же самой династии.
Напишите программу, которая найдёт распределение, соответствующее хотя бы одной из версий и имеющее наименьший показатель сомнительности, а также версию, которой оно соответствует.
Входные данные
В первой строке записано число n (2 ≤ n ≤ 200000) - количество праздников в летописи. Следующая строка содержит целые числа x[1], x[2], ..., x[n] (1 ≤ x[1] < x[2] < ... < x[n] ≤ 10^9) - годы проведения праздников.
В третьей строке записано число учёных s (1 ≤ s ≤ 50). В каждой из последующих s строк записаны четыре натуральных числа kl[i], kr[i], ml[i], mr[i] (1 ≤ kl[i] ≤ kr[i] ≤ 10^9), (1 ≤ ml[i] ≤ mr[i] ≤ 10^9).
Выходные данные
Первая строка должна содержать числа p и q, где p - номер учёного, версии которого соответствует распределение с наименьшим показателем сомнительности, а q - показатель сомнительности этого распределения.
Вторая строка должна состоять из n цифр 1 и 2, записанных без пробелов, означающих приход к власти представителя первой или второй династии соответственно. Если существует несколько решений с наименьшим показателем сомнительности q, выведите любое из них.
В случае, если ни в одной из версий учёных не существует способа распределения периодов правления между династиями так, чтобы не нарушались ограничения на промежутки времени между праздниками, выведите число 0.
Пример
3 1 2 3 1 1 1 1 1
1 1 122
4 1 6 9 13 2 1 2 2 3 6 7 3 3
0
5 3 6 8 9 10 2 2 3 1 1 1 4 1 10
2 0 21212