### 问题描述 已知在水平面上一块 $n\times m$ 的区域 $S$，$S$ 的左上角坐标为 $(1,1)$，右下角坐标为 $(n,m)$，每个**整数点坐标**占用 $1\times 1$ 的单元面积。 有 $k$ 种不同高度的积木 $k_i$，每种积木的长和宽都为 $1$，高度分别为 $h_i$。 现在每次可以在 $S$ 中选定一个矩形区域 $T(a,b,c,d)$ 和一种积木 $k_i$，可以让中所有 $T$ **整数点坐标**上都竖着放上一块 $k_i$ 的积木（可以不断往上堆）。  已知 $(a,b)$ 表示 $T$ 左上角坐标，$(c,d)$ 表示 $T$ 右下角坐标，满足 $1<=a<=c<=n$ 且 $1<=b<=d<=m$。 现在给定 $q$ 次操作： 操作 $1$：输入 $1$ 和 $T$ 的四个坐标值 $(a,b,c,d)$ 以及选定积木的编号 $k_i$。 操作 $2$：输入 $2$ 和 $T$ 的四个坐标值 $(a,b,c,d)$。 对于每次操作 $2$，请输出当前 $T$ 区域内所有积木体积之和。 ### 输入格式 输入第 $1$ 行包含四个正整数 $n,m,k,q$，分别表示 $S$ 区域的大小、积木的种数以及操作的次数 $(n,m\in[1,1000]，k\in[1,10^5]，q\in[1,2\times 10^5])$。 输入第 $2$ 行包含 $k$ 个积木的高度 $h_i(h_i\in[1,10^6])$。 第 $3\sim q+2$ 行每行输入均代表你需要进行的操作。 ### 输出格式 对于每个操作 $2$，输出仅一行，包含一个整数，表示答案。 ### 样例输入 ```text 2 2 1 2 3 1 1 1 2 2 1 2 1 1 2 2 ``` ### 样例输出 ```text 12 ```