Prof.Chen 赢得了 ICPC 区域赛冠军，并获得了明年参加 ICPC 全球总决赛的资格。为了在即将到来的全球总决赛中取得好成绩，他和队友们目前正在 Byteburg 参加 ICPC 总决赛前训练营。

Byteburg 是一座美丽的城市，拥有 $n$ 个令人惊叹的景点，编号为 $1, 2, \dots, n$。景点之间有 $n - 1$ 条双向道路，使得任意两个景点之间都可以直接或间接地连通。Byteburg 中最多有 50 个景点仅连接着一条道路。

不幸的是，一些（可能为零）景点目前不对游客开放。每天下午，在 5 小时的训练后，Prof.Chen 会浏览旅游网站查看哪些景点是开放的，然后制定一个班车游览计划。你需要执行 $q$ 次操作。每次操作为以下两种之一：

• “1 $x$” ($1 \le x \le n$)：改变第 $x$ 个景点的状态。如果它当前是开放的，则将其关闭，反之亦然。
• “2 $l$ $r$” ($1 \le l \le r \le n$)：Prof.Chen 计划乘坐班车访问索引在 $[l, r]$ 范围内的所有开放景点。班车将从某个地点出发，沿道路行驶，最后返回出发地点，使得每个开放景点至少被访问一次。注意，即使某个地点的景点是关闭的，班车仍然可以经过该地点。班车的出发地点和路线可以由 Prof.Chen 指定，他希望最小化路线的总长度。请编写一个程序来计算最短路线长度。

输入格式

第一行包含两个整数 $n$ 和 $q$ ($1 \le n, q \le 200\,000$)，分别表示景点数量和操作数量。

第二行包含一个长度为 $n$ 的字符串 $S$ ($S_i \in \{'0', '1'\}$)，表示第 $i$ 个景点最初的状态。其中，'0' 表示关闭，'1' 表示开放。

接下来的 $n - 1$ 行，每行包含三个整数 $u_i, v_i$ 和 $w_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i, 1 \le w_i \le 10^9$)，表示第 $u_i$ 个景点和第 $v_i$ 个景点之间有一条长度为 $w_i$ 的双向道路。保证任意两个景点之间都可以直接或间接地连通。

接下来的 $q$ 行，每行描述一个上述格式的操作。

保证最多有 50 个景点仅连接着一条道路。

输出格式

对于每次查询，输出一行，包含一个整数，表示最短路线的长度。注意，当索引在 $[l, r]$ 范围内的所有景点都关闭时，请输出 “-1”。

样例

输入格式 1

5 6
10110
1 2 1
1 3 10
2 4 100
3 5 1000
2 1 5
1 3
2 1 5
2 2 4
2 5 5
2 1 1

输出格式 1

222
202
0
-1
0