eolymp
Yarışlar

Queue Data Structure

Древние династии

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

История Татаро-монгольского ханства богата на правителей. Каждый из n правителей принадлежал к одной из двух династий, причём власть часто переходила от одной династии к другой. Каждое восхождение правителя на престол отмечалось праздником, проводимым 26 марта. В летописях зафиксированы годы проведения этих праздников, причем известно, что правители первой династии устраивали для народа праздник кумыса, а второй - праздник мёда.

На конференции по истории Татаро-монгольского ханства каждый из s учёных предложил свою версию толкования летописи. А именно, i-й историк утверждал, что от каждого праздника кумыса до следующего праздника кумыса проходило не менее kl[i] лет, но не более kr[i] лет, в то время как от каждого праздника мёда до следующего праздника мёда проходило не менее ml[i] лет, но не более mr[i] лет.

Каждой предложенной версии может соответствовать несколько распределений правителей по династиям. Ученые договорились считать показателем сомнительности распределения число переходов власти к представителю той же самой династии.

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

Giriş verilənləri

В первой строке записано число n (2n200000) - количество праздников в летописи. Следующая строка содержит целые числа x[1], x[2], ..., x[n] (1x[1] < x[2] < ... < x[n]10^9) - годы проведения праздников.

В третьей строке записано число учёных s (1s50). В каждой из последующих s строк записаны четыре натуральных числа kl[i], kr[i], ml[i], mr[i] (1kl[i]kr[i]10^9), (1ml[i]mr[i]10^9).

Çıxış verilənləri

Первая строка должна содержать числа p и q, где p - номер учёного, версии которого соответствует распределение с наименьшим показателем сомнительности, а q - показатель сомнительности этого распределения.

Вторая строка должна состоять из n цифр 1 и 2, записанных без пробелов, означающих приход к власти представителя первой или второй династии соответственно. Если существует несколько решений с наименьшим показателем сомнительности q, выведите любое из них.

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

Nümunə

Giriş verilənləri #1
3
1 2 3
1
1 1 1 1
Çıxış verilənləri #1
1 1
122
Giriş verilənləri #2
4
1 6 9 13
2
1 2 2 3
6 7 3 3
Çıxış verilənləri #2
0
Giriş verilənləri #3
5
3 6 8 9 10
2
2 3 1 1
1 4 1 10
Çıxış verilənləri #3
2 0
21212
Mənbə 2013 XXV Всероссийская олимпиада по информатике, 26 марта, Задача D