题目描述

鞑靼-蒙古汗国的历史上有许多统治者。$N$ 位统治者中的每一位都属于两个王朝之一，而且权力经常从一个王朝转移到另一个王朝。

每位统治者登基都会在 3 月 26 日举行庆典来纪念。编年史中记录了这些庆典举行的年份，且已知第一个王朝的统治者为人民举办马奶节，而第二个王朝则举办蜂蜜节。

在关于鞑靼-蒙古汗国历史的会议上，$S$ 位学者中的每一位都提出了自己对编年史的解释版本。具体来说，第 $i$ 位历史学家声称：从每个马奶节到下一个马奶节间隔不少于 $KL_i$ 年但不超过 $KR_i$ 年，而从每个蜂蜜节到下一个蜂蜜节间隔不少于 $ML_i$ 年但不超过 $MR_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$ 行中每行写有四个自然数 $KL_i$, $KR_i$, $ML_i$, $MR_i$（$1 \le KL_i \le KR_i \le 10^9$），（$1 \le ML_i \le MR_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

提示

评分

本题包含五个子任务。每个子任务的评分使用独立的测试组。仅当通过该组所有测试时，子任务的得分才会被计入。

子任务 1

$2 \le N \le 15$，$1 \le S \le 10$。 该子任务分值为 20 分。

子任务 2

$2 \le N \le 2000$，$1 \le S \le 50$，$N\times S \le 2000$。 该子任务分值为 20 分。

子任务 3

$2 \le N \le 10,000$，$1 \le S \le 50$，$N\times S \le 10,000$。 该子任务分值为 20 分。

子任务 4

$2 \le N \le 200,000$，$1 \le S \le 50$，$N\times S \le 200,000$。 该子任务分值为 20 分。

子任务 5

$2 \le N \le 200,000$，$1 \le S \le 50$。 该子任务分值为 20 分。