遥远

(distance.cpp 3s/512MB)

题目描述

小 X 非常喜欢跳棋，这天她设计了一个 $n\times n\times n$ 的立方体棋盘，每个格点都可以用一个三元组坐标 $(i,j,k)$ 表示，其中 $1\le i,j,k\le n$。某些格子上摆放着棋子，但是小 X 只想移动其中的一枚。一个初始时位于格点 $(a,b,c)$ 的棋子一次移动可以走向没有棋子的格点 $(x,y,z)$ 当且仅当 $a\not= x,b\not= y,c\not=z$ 三者中有且仅有一个成立（即只有一维坐标不同）并且 $(a,b,c)$ 到 $(x,y,z)$ 的线段（不包含端点）上存在恰好偶数枚棋子。

现在，告诉你棋盘上棋子的数量以及它们所处的格点位置，小 X 想移动的棋子的编号是 $x$，同时她不希望棋子的位置太过遥远，所以她决定至多移动 $k$ 次，在此过程中你不能移动除了 $x$ 以外的任何棋子。在此前提下，你能告诉她编号 $x$ 的棋子可能到达多少个不同的格点吗？

输入格式

第一行包含四个整数 $n,m,k,x$，分别表示棋盘的边长、棋子总数、最多允许的移动次数和小 X 想移动的棋子的编号。

接下来 $m$ 行，第 $t$ 行包含三个正整数，表示第 $t$ 枚棋子所在的格点坐标 $(i_t, j_t, k_t),1\le i_t,j_t,k_t\le n$。保证不存在两枚棋子所在的格点坐标相同。

输出格式

输出一个整数，表示在最多移动 $k$ 步的前提下，第 $x$ 枚棋子最多可以到达多少个不同的格点（含初始位置）。

输入输出样例 #1

样例输入#1

4 6 1 1
1 2 2
2 2 2
3 2 2
1 3 2
1 2 3
4 4 4

样例输出#1

4

样例说明#1

从 $(1,2,2)$ 走一步可以到达 $(1,2,2),(4,2,2),(1,1,2),(1,2,1)$。

输入输出样例 #2

样例输入#2

5 31 2 1
3 3 3
2 3 3
4 3 3
2 2 3
4 2 3
2 4 3
4 4 3
3 2 2
3 2 4
3 4 2
3 4 4
2 3 2
4 3 2
2 3 4
4 3 4
2 1 3
4 1 3
2 5 3
4 5 3
3 1 2
3 1 4
3 5 2
3 5 4
2 3 1
4 3 1
2 3 5
4 3 5
3 2 1
3 4 1
3 2 5
3 4 5

样例输出#2

9

数据范围

对于 $30\%$ 的数据，$n,k\le 5$。

对于 $70\%$ 的数据，$n\le 60$。

对于 $100\%$ 的数据，$n\le 250,m\le \min(n^3,10^5),k\le n^3$。