| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 11 | 6 | 4 | 57.143% |
История Татаро-монгольского ханства богата на правителей. Каждый из $N$ правителей принадлежал к одной из двух династий, причём власть часто переходила от одной династии к другой. Каждое восхождение правителя на престол отмечалось праздником, проводимым 26 марта. В летописях зафиксированы годы проведения этих праздников, причем известно, что правители первой династии устраивали для народа праздник кумыса, а второй --- праздник мёда.
На конференции по истории Татаро-монгольского ханства каждый из $S$ учёных предложил свою версию толкования летописи. А именно, $i$-й историк утверждал, что от каждого праздника кумыса до следующего праздника кумыса проходило не менее $K\!L_i$ лет, но не более $K\!R_i$ лет, в то время как от каждого праздника мёда до следующего праздника мёда проходило не менее $M\!L_i$ лет, но не более $M\!R_i$ лет.
Каждой предложенной версии может соответствовать несколько распределений правителей по династиям. Ученые договорились считать показателем сомнительности распределения число переходов власти к представителю той же самой династии.
Требуется написать программу, которая найдёт распределение, соответствующее хотя бы одной из версий и имеющее наименьший показатель сомнительности, а также версию, которой оно соответствует.
В первой строке входного файла записано число $N$ (2ドル \le N \le 200,000円$) --- количество праздников в летописи. Следующая строка содержит целые числа $X_1, X_2, \ldots, X_N$ (1ドル \le X_1 < X_2 < \ldots < X_N \le 10^9$) --- годы проведения праздников.
В третьей строке записано число учёных $S$ (1ドル \le S \le 50$). В каждой из последующих $S$ строк записаны четыре натуральных числа $K\!L_i,ドル $K\!R_i,ドル $M\!L_i,ドル $M\!R_i$ (1ドル \le K\!L_i \le K\!R_i \le 10^9$), (1ドル \le M\!L_i \le M\!R_i \le 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