背景

MT学校准备组织小学生们下个假期一起去旅游!

描述

MT学校的校长ZTM计划着让小学生们在全国各地进行旅行。全国一共有N个景点,编号为1~N,由M条双向道路相连。ZTM学校一共有K个小学生,编号为1~K,每个小学生有一个体力值上限Pi。每次旅行的起点是编号为u的景点,终点是编号为v的景点。每次旅行开始时,小学生们都在编号为u的景点,初始体力值为Pi。小学生们每经过一个景点,都会把体力值恢复到上限。小学生们每走过一个单位长度的路径,都会消耗1点体力值。当然,他们的体力值必须时时刻刻大于等于0。小学生们都很聪明,只要存在一条路径使得他们能成功从u走到v,他们就一定能完成这次旅行。

下个假期一共有Q天,每天会发生下面两种事件之一:第一种事件是编号为x的小学生因为某些原因,体力值上限变成了p;第二种事件是校长ZTM组织小学生们进行旅行,起点是景点u,终点是景点v。

校长ZTM想知道,每次旅游有多少个小学生可以成功从景点u走到景点v?

输入格式

第一行有三个整数N, M, K, Q,同题目所述;

第二行到第M + 1行,每行有三个整数u, v, l,表示景点u到景点v有一条双向路径,有l个单位长度;

之后的K行,第i + M + 1行一个整数,表示编号为i的小学生的体力上限Pi;

最后Q行,第i + K + M + 1行的第一个整数q,表示第i天发生的事件种类:

如果q = 1,后面两个整数x, p,表示编号为x的小学生的体力上限变成了p;

如果q = 2,后面两个整数u, v,表示ZTM组织了一次从景点u到景点v的旅行。

输出格式

对于每次旅行,输出一行一个整数表示有多少个小学生能完成这次旅行。

样例输入

5 6 5 5
1 2 4
2 4 5
1 3 2
1 5 7
3 5 3
4 5 6
1
2
3
4
5
2 1 5
2 2 4
2 2 5
1 2 4
2 2 5

样例输出

3
1
2
3

数据范围与约定

对于100%的数据,

2 <= N <= 100000,1 <= M <= 200000,1 <= Q <= 200000,1 <= K <= 200000,0 <= l <= 200000,1 <= x <= K,

保证每天每个小学生的体力上限都大于等于0且小于等于109,1 <= u, v <= N,u ≠ v,可能有重边,保证图是联通的。

单点时间限制1s。

来源

原创