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

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

1. (1, x, y, z)_{}(1,x,y,z), meaning to add a tag on position (x, y, z)_{}(x,y,z) in the cube
2. (2,x, y, z)_{}(2,x,y,z), meaning to determine the minimum Manhattan Distance to the given position (x, y, z)_{}(x,y,z) among all tagged positions

Manhattan Distance between two positions (x_1, y_1, z_1), (x_2, y_2, z_2)(x1,y1,z1),(x2,y2,z2) is defined as |x_1 - x_2| + |y_1 - y_2| + |z_1 - z_2|∣x1−x2∣+∣y1−y2∣+∣z1−z2∣.

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_{}n,m,h,q, denoting the sizes in three dimensions of the cube and the number of instructions.
	


	

		
	


	

		Following q_{}q lines each contains four positive integers op,x, y, z_{}op,x,y,z, where op=1_{}op=1 means to add a tag on (x,y,z)_{}(x,y,z) while op=2_{}op=2 means to make a query on (x,y,z)_{}(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 h1≤n×m×h,q≤105,1≤x≤n,1≤y≤m,1≤z≤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

输入

复制 
3 3 3 4
1 1 1 1
2 2 3 3
1 3 1 1
2 3 3 2

输出

复制 
5
3

说明 

					

						For the first query, there is only one tagged position (1,1,1)_{}(1,1,1) currently, so the answer is |1-2| + |1-3| + |1-3| = 5_{}∣1−2∣+∣1−3∣+∣1−3∣=5.
					


					

						
					

For the second query, (3,1,1)_{}(3,1,1) is the nearest tagged position, so the answer is |3-3| + |1-3| + |1-2| = 3_{}∣3−3∣+∣1−3∣+∣1−2∣=3.

定期bfs处理，期限内暴力枚举 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll mod=1e9+7;
const int modp=998244353;
const int maxn=1e5+50;
const double eps=1e-6;
#define lowbit(x)  x&(-x)
#define INF 0x3f3f3f3f
const double inf=0x7fffffff;
inline ll read()
{
    ll x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
int dcmp(double x)
{
    if(fabs(x)<eps)return 0;
    return (x>0)?1:-1;
}
int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}
ll qmod(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1)
        {
            ans=(ans*a)%mod;
        }
        b>>=1;
        a=(a*a)%mod;
    }
    return ans;
}
const int maxs=1000;
int dx[]= {1,-1,0,0,0,0};
int dy[]= {0,0,1,-1,0,0};
int dz[]= {0,0,0,0,1,-1};
int dis[maxn],n,m,h,q;
vector<int>X,Y,Z;
struct node
{
    int x,y,z;
};
int myhash(int x,int y,int z)
{
    return x*m*h+y*h+z;
}
void bfs()
{
    queue<node>q;
    for(int i=0; i<maxs; ++i)
    {
        dis[myhash(X[i],Y[i],Z[i])]=0;
        q.push({X[i],Y[i],Z[i]});
    }
    while(!q.empty())
    {
        node tmp=q.front();
        q.pop();
        for(int i=0; i<6; ++i)
        {
            int nx=tmp.x+dx[i],ny=tmp.y+dy[i],nz=tmp.z+dz[i];
            if(nx<0||ny<0||nz<0||nx>=n||ny>=m||nz>=h||dis[myhash(nx,ny,nz)]<=dis[myhash(tmp.x,tmp.y,tmp.z)]+1)continue;
            dis[myhash(nx,ny,nz)]=dis[myhash(tmp.x,tmp.y,tmp.z)]+1;
            q.push({nx,ny,nz});
        }
    }
    X.clear();
    Y.clear();
    Z.clear();
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&h,&q);
    int op,x,y,z,ans;
    memset(dis,INF,sizeof(dis));
    while(q--)
    {
        scanf("%d%d%d%d",&op,&x,&y,&z);
        x--;y--;z--;
        if(op==1)
        {
            X.push_back(x);
            Y.push_back(y);
            Z.push_back(z);
        }
        else
        {
            ans=dis[myhash(x,y,z)];
            int len=X.size();
            for(int i=0; i<len; i++)
            {
                ans=min(ans,abs(x-X[i])+abs(y-Y[i])+abs(z-Z[i]));
            }
            printf("%d\n",ans);
        }
        if(X.size()==maxs)
        {
            bfs();
        }
    }
    return 0;
}