题目描述

Koishi 决定走出幻想乡成为数学大师！

Flandre 听说她数学学的很好，就给 Koishi 出了这样一道构造题：

Task1：试判断能否构造并构造一个长度为 $n$ 的 $1 \dots n$ 的排列，满足其 $n$ 个前缀和在模 $n$ 的意义下互不相同。

Task2：试判断能否构造并构造一个长度为 $n$ 的 $1 \dots n$ 的排列，满足其 $n$ 个前缀积在模 $n$ 的意义下互不相同。

按照套路，Koishi 假装自己根本不会捉，就来找你帮忙辣。

输入格式

第一行两个整数 $X$ 和 $T$，分别表示 Task 类型和测试点内的数据组数。

接下来 $T$ 行，每行一个整数表示每组数据中的 $n$。

输出格式

为了方便 SPJ 的编写，您需要遵从以下格式输出。

对于每组数据仅包含一行输出：

1. 如果您认为当前数据不存在符合题意的构造，只需输出一个整数 $0$。
2. 如果您认为当前数据存在符合题意的构造却不会构造，只需输出一个整数 $1$。
3. 如果您认为当前数据存在符合题意的构造并成功构造，则需要先输出一个整数 $2$，再输出 $n$ 个整数表示构造的方案。

每两个整数之间需要有空格作为分隔符。

说明/提示

对于每组数据：

1. 如果您对于构造的存在性判断正确，您将会得到 $30\%$ 的分数，若您的构造符合题意或者确实不存在符合题意的构造，您将会得到剩余的 $70\%$ 的分数。
2. 如果您对于构造的存在性判断不正确，您将不会得到任何分数。

对于每组测试点，您的得分将是本组数据点中得分的最小值。

测试点类型 $1$：$10$ 分，满足 $X = 1$，$1 \leq n \leq 10$。
测试点类型 $2$：$40$ 分，满足 $X = 1$，$1 \leq n \leq {10}^5$。
测试点类型 $3$：$10$ 分，满足 $X = 2$，$1 \leq n \leq 10$。
测试点类型 $4$：$40$ 分，满足 $X = 2$，$1 \leq n \leq {10}^5$。

对于所有测试点，满足 $1 \leq T \leq 10$。

样例

1 1
8

2 8 7 6 5 4 3 2 1

2 1
11

2 1 2 3 5 10 6 7 4 9 8 11