分数: 500 点
问题陈述
有 N 三维空间中的长方体。
这些长方体不重叠。 形式上,对于其中任意两个不同的长方体,它们的交集的体积为 0.
的对角线 i第一个长方体是连接两个点的线段 (X_{i,1},Y_{i,1},Z_{i,1}) 和 (X_{i,2},Y_{i,2},Z_{i,2}),其边缘均平行于其中一个坐标轴。
对于每个长方体,找到与其共享一个面的其他长方体的数量。
正式地,对于每个 i,查找数量 j 与 1\leq j \leq N 和 j\neq i 使得表面的交集 i-th 和 j第一个长方体的面积为正。
约束
- 1 \leq N \leq 10^5
- 0 \leq X_{i,1} < X_{i,2} \leq 100
- 0 \leq Y_{i,1} < Y_{i,2} \leq 100
- 0 \leq Z_{i,1} < Z_{i,2} \leq 100
- 长方体与正体积没有交集。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N
X_{1,1} Y_{1,1} Z_{1,1} X_{1,2} Y_{1,2} Z_{1,2}
\vdots
X_{N,1} Y_{N,1} Z_{N,1} X_{N,2} Y_{N,2} Z_{N,2}
输出
打印答案。
示例输入 1
4 0 0 0 1 1 1 0 0 1 1 1 2 1 1 1 2 2 2 3 3 3 4 4 4
示例输出 1
1 1 0 0
的 1-st 和 2-nd 长方体共享一个矩形,其对角线是连接两点的线段 (0,0,1) 和 (1,1,1).
的 1-st 和 3-rd 长方体共享一个点 (1,1,1),但不共享表面。
示例输入 2
3 0 0 10 10 10 20 3 4 1 15 6 10 0 9 6 1 20 10
示例输出 2
2 1 1
示例输入 3
8 0 0 0 1 1 1 0 0 1 1 1 2 0 1 0 1 2 1 0 1 1 1 2 2 1 0 0 2 1 1 1 0 1 2 1 2 1 1 0 2 2 1 1 1 1 2 2 2
示例输出 3
3 3 3 3 3 3 3 3