Давні династії
Історія Татаро-монгольського ханства багата на правителів. Кожен із 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.