D-Distance_2019牛客暑期多校训练营（第八场）

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

Gromah and LZR have entered the fourth level. There is a blank cube with size $n\times m\times h$ hanging on the wall.

Gromah soon finds a list beside the cube, there are $q_{}$ instructions in the list and each instruction is in one of the following two formats:

1. $(1, x, y, z)_{}$ , meaning to add a tag on position $(x, y, z)_{}$ in the cube

2. $(2,x, y, z)_{}$ , meaning to determine the minimum Manhattan Distance to the given position $(x, y, z)_{}$ among all tagged positions

Manhattan Distance between two positions $(x_1, y_1, z_1), (x_2, y_2, z_2)$ is defined as $|x_1 - x_2| + |y_1 - y_2| + |z_1 - z_2|$ .

LZR also finds a note board saying that the password of this level is the sequence made up of all results of the instructions in format 2.

Please help them get all results of the instructions in format 2.

输入描述:

The first line contains four positive integers $n,m,h,q_{}$ , denoting the sizes in three dimensions of the cube and the number of instructions.

Following $q_{}$ lines each contains four positive integers $op,x, y, z_{}$ , where $op=1_{}$ means to add a tag on $(x,y,z)_{}$ while $op=2_{}$ means to make a query on $(x,y,z)_{}$ .

$1 \le n\times m\times h, q\le 10^5, 1 \le x \le n, 1 \le y \le m, 1 \le z \le h$

It is guaranteed that the first instruction is in format 1 and that no position will be tagged more than once.

输出描述:

For each instruction in format 2, output the answer in one line.

示例1

输入

复制

输出

复制

5
3

说明

For the first query, there is only one tagged position  currently, so the answer is .

For the second query,  is the nearest tagged position, so the answer is .