当前没有测试数据。

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

已知城市 H 中有 $n$ 个商店，$m$ 条街道。每条街道长 $W_i$ 每个商店中都有一个礼品值表示小 Z 对该商店的礼品的喜爱程度 $C_i$ 。现在小 Y 想让小 Z 尽可能的高兴 。小 Y 从某一号商店出发，走到无路可走为止。求小 Z 的最大幸福程度。幸福程度 $=$ 对已购买礼品的快乐程度之和。（ 对礼品快乐程度 $=$ 对礼品的喜爱程度 $×$ 该礼品被买了之后经过的下一条街道的长度 ）

现在，小 Y 到 $A_i$ 号商店时，所拥有的幸福程度都会面临一次“施法”：
1、所拥有的幸福程度进行一次开平方操作。
2、所拥有的幸福程度进行一次平方操作。

• 保证商店及其街道构成一个有向无环图。
• 开平方操作结果保留整数。

Format

Input

第一行一个整数 $n$ 表示商店数。
第二行 $n$ 个数，第 $i$ 个数表示 $C_i$。
第三行一个整数 $m$ 表示街道数。
接下来 $m$ 行，每行 $3$ 个整数 $u,v,W_i$ 表示存在一条由 $u$ 号商店到 $v$ 号商店，距离为 $W_i$ 的道路。
接下来一行一个整数 $t$ 表示操作的个数。
接下来 $t$ 行，每行 $2$ 个整数。
1、 1 X 经过 $X$ 号商店时进行开平方操作
2、 2 Y 经过 $Y$ 号商店时进行平方操作

Output

一行一个整数表示小 Z 的最大幸福程度。

Samples

5
8 7 6 5 4
4
1 3 2
2 3 3
3 4 4
3 5 5
0

51

4
10 5 4 6
3
1 2 10
2 3 6
3 4 8
2
2 2
1 3

132