G. 礼物

传统 1000 ms 256 MiB
标准 IO
Special Judge

题目描述

小 S 设计了一道题目,准备作为礼物送给大家。

给定一个长度为 nn 的整数序列 a1,a2,,ana_1,a_2,\cdots,a_n

输出它的任意一个满足以下要求的非空子序列 ab1,ab2,,abka_{b_1},a_{b_2},\cdots,a_{b_k}

(i=1kabi)modn=0\left(\sum_{i=1}^ka_{b_i}\right)\bmod n=0

可以证明,这样的子序列一定存在。

小 L 看完题目后,向大家解释了一些基本概念:

任取整数 kk 满足 1kn1\le k\le n,以及 kk 个整数 b1,b2,,bkb_1,b_2,\cdots,b_k 满足

1b1<b2<<bkn1\le b_1<b_2<\cdots<b_k\le n

则称 ab1,ab2,,abka_{b_1},a_{b_2},\cdots,a_{b_k}a1,a2,,ana_1,a_2,\cdots,a_n 的一个非空子序列。

关于求和号 \sum,它的含义是

i=1kabi=ab1+ab2++abk\sum_{i=1}^ka_{b_i}=a_{b_1}+a_{b_2}+\cdots+a_{b_k}

在这里,mod\bmod 运算的定义是

xmody=xxyyx\bmod y=x-\left\lfloor\frac{x}{y}\right\rfloor y

其中 z\lfloor z\rfloor 表示 z\le z 的最大整数。xmody=0x\bmod y=0 等价于 xxyy 的倍数。

输入格式

第一行一个整数 TTT1T\ge1),表示该测试点有 T\boldsymbol{T} 组数据

接下来,对于每组数据:

  • 第一行一个整数 nnn1n\ge1)。
  • 第二行 nn 个整数 a1,a2,,ana_1,a_2,\cdots,a_n1ai1091\le a_i\le10^9)。

保证 TT 组数据中的 nn 之和 n106\sum n\le10^6

输出格式

对于每组数据,输出两行:

  • 第一行一个整数 kk
  • 第二行 kk 个整数 b1,b2,,bkb_1,b_2,\cdots,b_k

你需要保证:

  • 1kn1\le k\le n
  • 1b1<b2<<bkn1\le b_1<b_2<\cdots<b_k\le n
  • (ab1+ab2++abk)modn=0(a_{b_1}+a_{b_2}+\cdots+a_{b_k})\bmod n=0

若有多个解,只需输出任意一个。

样例

输入

2
6
1 1 4 5 1 4
6
1 1 4 5 1 4

一个满足要求的输出

2
2 4
5
1 2 3 4 5

解释

在第一组数据中,a2+a4=1+5=6a_2+a_4=1+5=66mod6=06\bmod6=0,满足要求。

在第二组数据中,a1+a2+a3+a4+a5=1+1+4+5+1=12a_1+a_2+a_3+a_4+a_5=1+1+4+5+1=1212mod6=012\bmod6=0,满足要求。