问题描述

中秋节的晚上，dd_engi在桌面上放了许多好看的彩灯。遗憾的是，这些彩灯可能并非全部都亮着。于是，你打算把全部这些彩灯都点亮。

但是，你很快发现，这些彩灯的摆放是非常有规律的，事实上，彩灯的位置都在平面的正三角形镶嵌的某个交点处。距离为单位长度的彩灯被认为相互相邻。可以看出，每个彩灯最多与六个彩灯相邻，相邻的彩灯都在以其为中心的单位正六边形的顶点上。

下图就是一种合法的彩灯摆放（对应样例数据）：

其中，实心和空心的圆点分别代表亮与灭的彩灯，实线边代表彩灯间的相邻关系。

图中的边组成了若干单位正三角形（边长为单位长度的三角形），可以看出，每个彩灯与它相邻的彩灯最多可以组成六个单位正三角形。而所有的单位三角形可被分成两类，我们称为A类以及B类，图中加阴影的三角形属于A类。A类三角形的特征是，三个顶点分别在上方、左下方及右下方。

每个A类三角形中有一个开关（图中未画出），dd_engi告诉你，按动三角形中的开关开关会改变三个顶点上每个彩灯的亮灭状态（亮变成灭，灭变成亮）。

那么，要点亮所有彩灯，最少需要按动多少次开关呢？

输入格式

输入数据描述了每个彩灯的初始亮灭状态以及所有三角形。

第一行一个整数N，表示彩灯的数目，彩灯被编号为1至N。

第二行N个0或1的整数，第i个0或1表示第i个彩灯初始的状态是灭或亮。

第三行一个整数M，表示有M对彩灯相邻的关系。

以下M行，每行三个整数，表示一对彩灯相邻的关系。前两个整数即相邻的这一对彩灯的编号。第三个整数表示第二个彩灯相对于第一个彩灯的方位，0~5分别表示右方、右下、左下、左方、左上、右上。例如，“1 3 1”表示“第3个彩灯在第1个彩灯的右下方”。

输出格式

如果不可能做到点亮所有彩灯，输出-1，否则输出最小的步数。

样例输入

11

0 1 0 0 1 0 1 0 1 0 1

20

1 2 2

1 3 1

2 3 0

2 4 2

2 5 1

4 5 0

3 5 2

3 6 1

5 6 0

7 6 3

8 4 4

5 8 2

5 9 1

8 9 0

6 9 2

6 10 1

9 10 0

10 7 5

11 8 4

11 9 5

样例输出

4

数据范围

对于30%的数据，N<=100。

对于100%的数据，3<=N<=50000。