#P3599. Koishi Loves Construction

    ID: 5143 远端评测题 1000ms 125MiB 尝试: 2 已通过: 0 难度: 10 上传者: 标签>数学洛谷原创Special Judge洛谷月赛

Koishi Loves Construction

题目描述

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

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

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

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

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

输入格式

第一行两个整数 XXTT,分别表示 Task 类型和测试点内的数据组数。

接下来 TT 行,每行一个整数表示每组数据中的 nn

输出格式

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

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

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

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

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

提示

对于每组数据:

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

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

测试点类型 111010 分,满足 X=1X = 11n101 \leq n \leq 10
测试点类型 224040 分,满足 X=1X = 11n1051 \leq n \leq {10}^5
测试点类型 331010 分,满足 X=2X = 21n101 \leq n \leq 10
测试点类型 444040 分,满足 X=2X = 21n1051 \leq n \leq {10}^5

对于所有测试点,满足 1T101 \leq T \leq 10