题目描述

有一个 $n\times n\times n$ 的三维矩阵，需要在若干个格子中放置摄像头。

一个摄像头的拍摄范围是它所在的一行，一列以及一纵列（即可以往 $6$ 个方向看，同时也能看到自己）。

目标是使得这个矩阵不存在摄像头看不到的位置。

构造一种方案，使得摄像头数量尽量少。

输入格式

第一行一个正整数 $n$ 表示这个三维矩阵的边长为 $n$。

输出格式

第一行一个正整数 $t$ 表示你的方案中摄像头的个数。

接下来 $t$ 行，每行三个在 $[1,n]$ 中的整数 $x,\,y,\,z$ 表示一个摄像头的坐标。

2

2
1 1 1
2 2 2

数据范围与提示

对于所有数据，$1\leq n\leq 2000$。

本题设有部分分，对于一个测试点，若你的答案为$x$且方案合法，你将获得以下比例的得分：

$$rate=\begin{cases} 1 & x<\lceil 0.5n^2\rceil \\ 1 & x=\lceil 0.5n^2\rceil \\ 0.8\times(\frac{\lceil 0.5n^2\rceil}{x})^3 & x>\lceil 0.5n^2\rceil \end{cases}$$

对于任意一个子任务，你的得分为其所有测试点得分的最小值。

子任务编号	分值	$n \leq$	特殊限制
1	$10$	$10$	-
2		$50$	$n$ 为偶数
3			$n$ 为奇数
4	$15$	$300$	$n$ 为偶数
5			$n$ 为奇数
6	$20$	$2000$	$n$ 为偶数
7			$n$ 为奇数

注意：如果你的方案不够优，输出会非常庞大，建议使用必要的输出优化。