The history of the Tatar-Mongol Khanate is rich in rulers. Each of the n rulers belonged to one of the two dynasties, and power often passed from one dynasty to another. Each ascension of the ruler to the throne was marked by a holiday held on March 26. The annals recorded years of these holidays, and it is known that the rulers of the first dynasty organised a koumiss festival for the people, and rulers of the second dynasty organised a honey festival.

At conference on the history of the Tatar-Mongol Khanate, each of s scientists proposed their own version of the interpretation of the chronicle. Namely, i-th historian argued that from each koumiss holiday until the next koumiss holiday, at least kli years passed, but not more than kri years, while from each the holiday of honey until the next holiday of honey took at least mli years, but no more than mri years.

Each proposed version can correspond to several distributions of rulers by dynasties. Scientists have agreed to consider the indicator of the doubtfulness the distribution of the number of transitions of power to a representative of the same dynasty.

Write a program that will find the distribution corresponding to at least one of the versions and having the lowest index of doubtfulness, as well as the version to which it corresponds.

Input

First line contains number n (2 ≤ n ≤ 200000) - the number of holidays in the annals. Next line contains integers x1, x2, ..., xn (1 ≤ x1 < x2 < ... < xn ≤ 109) - the years of holidays.

Third line contains the number of scientists s (1 ≤ s ≤ 50). Each of the next s lines contains four positive integers kli, kri, mli, mri (1 ≤ kli ≤ kri ≤ 109), (1 ≤ mli ≤ mri ≤ 109).

Output

First line must contain numbers p and q, where p is the number of scientist, which version corresponds to the distribution with the lowest doubtfulness index, and q is the indicator of doubtfulness of this distribution.

Second line must consist of n digits of 1 and 2 without spaces, meaning the coming to power of a representative of the first or second dynasty, respectively. If there are several solutions with the smallest doubtfulness q, output any of them.

In the case if there is no way for the distribution of periods of government between dynasties in any version of scholars so that the restrictions on the intervals between holidays are violated, output the number 0.