题目描述

译自 ROI 2013 Day1 T4. Древние династии

鞑靼-蒙古汗国的历史上有许多统治者。共有 $N$ 位统治者，每位统治者属于两个王朝之一，权力常常在两个王朝之间交替。每位统治者登基时都会在 3 月 26 日举行庆典。史书中记录了这些庆典的年份，并且已知第一王朝的统治者会举办马奶酒庆典，而第二王朝的统治者则举办蜂蜜庆典。

在鞑靼-蒙古汗国历史会议上，有 $S$ 位学者提出了各自对史书的解读版本。第 $i$ 位历史学家认为，从一个马奶酒庆典到下一个马奶酒庆典的时间间隔不少于 $KL_i$ 年，但不多于 $KR_i$ 年；而从一个蜂蜜庆典到下一个蜂蜜庆典的时间间隔不少于 $ML_i$ 年，但不多于 $MR_i$ 年。

每种解读版本可能对应多种统治者王朝分配方案。学者们一致同意将分配方案的可疑度指标定义为权力在同一王朝代表之间过渡的次数。

你需要编写一个程序，找到符合至少一种版本的分配方案，且其可疑度指标最小，同时输出对应的版本。

输入格式

输入文件的第一行包含一个整数 $N$ $(2 \leq N \leq 200000)$，表示史书中记录的庆典数量。

第二行包含 $N$ 个整数 $X_1, X_2, \ldots, X_N$ $(1 \leq X_1 < X_2 < \ldots < X_N \leq 10^{9})$，表示庆典举办的年份。

第三行包含一个整数 $S$ $(1 \leq S \leq 50)$，表示学者的数量。

接下来的 $S$ 行，每行包含四个自然数 $KL_i, KR_i, ML_i, MR_i$ $(1 \leq KL_i \leq KR_i \leq 10^{9}, 1 \leq ML_i \leq MR_i \leq 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

数据范围与提示

详细子任务附加限制及分值如下表所示：