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

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

• $2 \le N \le 200\\,000$, $1 \le S \le 50$