背景

二十载紫金征途，每一分都是淬火的回响。

题目描述

科比有 $n$ 场比赛记录，按时间顺序排列。第 $i$ 场得分为 $a_i$，且每场得分为正。他要将这些比赛分成至多 $k$ 段连续的时期，每段至少包含一场比赛。设最终分成 $t$ 段，第 $i$ 段的总得分为 $S_i$。

球迷写下 $m$ 条“曼巴法则”。每条法则给出三个整数 $x,y,p$：

• 若 $p=0$，第 $x$ 段总分必须小于第 $y$ 段总分；
• 若 $p=1$，第 $x$ 段总分必须大于第 $y$ 段总分。

若某条法则提到的 $x$ 或 $y$ 大于实际段数 $t$，该法则自动无效；否则必须满足。

一段时期的统治力是该段总得分的平方。求所有合法划分中，各段统治力之和的最大值。若不存在合法划分，输出 $-1$。

输入格式

第一行三个整数 $n, k, m$。
第二行 $n$ 个整数，第 $i$ 个整数表示第 $i$ 场比赛的得分 $a_i$。
接下来 $m$ 行，每行三个整数 $x, y, p$，其中 $p \in \{0, 1\}$：

• 若 $p = 0$，则法则为第 $x$ 时期的总得分 小于 第 $y$ 时期的总得分（即 $S_x < S_y$）；
• 若 $p = 1$，则法则为第 $x$ 时期的总得分 大于 第 $y$ 时期的总得分（即 $S_x > S_y$）。

输出格式

一行一个整数，表示最大统治力总和。若无解，输出 -1。

1 1 1
1
1 1 0

-1

5 5 3
3942 1676 1134 2418 905 
4 3 1
2 5 1
2 3 0

101505625

提示

对于 $100\%$ 的数据，$1\le n,k\le 5\times 10^5$，$0\le m\le 5\times 10^5$，$0< a_i\le 10^9$。

::cute-table{tuack} | 子任务编号 | $n$ | $k$ | $m$ | $a_i$ | 分值 | |:-:|:-:|:-:|:-:|:-:|:-:| | $1$ | $\le 15$ | $\le 15$ | $\le 15$ | $\le 10^6$ | $25$ | | $2$ | 无特殊限制 | 无特殊限制 | $=0$ | 无特殊限制 | $25$ | | $3$ | ^ | $=1$ | 无特殊限制 | ^ | $25$ | | $4$ | ^ | 无特殊限制 | ^ | ^ | $25$ |

温馨提示：请注意答案的数量级。在 C++ 中可以使用 __int128 类型存储和运算 $2^{127}-1$ 级别的数字。你可以在主函数前加上以下内容来读入和输出 __int128 类型的变量：

__int128 in()
{
    __int128 k=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
    return k*f;
}
void out(__int128 x)
{
    if(x<0)putchar('-'),x=-x;
    if(x<10)putchar(x+'0');
    else out(x/10),putchar(x%10+'0');
}
/*
使用方法：
输入：a=in();
输出：out(a);
*/