是牛牛还是狗勾

题号：NC260455
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

小狗勾灵机一动，这是一道绝世好题！

牛牛，又名斗牛，是一种简单却又非常有意思的棋牌游戏,最早起源于我国广东、广西和湖南三省，是一款地方性十足、游戏速度极快、刺激而惊险的棋牌游戏
简要规则如下：

玩家每人发放 $5$ 张卡牌，每张牌的数字只有 $1$ 到 $10$

玩家需要将手中的其中三张牌作为第一部分，剩余两张牌作为第二部分，玩家的目标是使得手中的牌型尽可能的大，谁的牌型更大谁就获胜

第一部分——【凑十】：牌的数字总和必须为 $10$ 的正整数倍

第二部分——【凑牌型】：牌的数字总和对 $10$ 取模得到的数字 $X$ 就是牛 $X$ ， $X$ 的数字大小体现了牌型大小

特殊的，对于第一部分，如果凑不出来 $10$ 的正整数倍，就是没有牛，是最小的一种牌型

特殊的，对于第二部分，如果 $X=0$ ，并且凑的出来第一部分，这种情况称为牛牛，是最大的一种牌型

所以，牌型大小为：没有牛<牛一<牛二<牛三<…<牛八<牛九<牛牛

（为简化题目，我们省略了花色以及其它特殊牌型的比较规则）

师傅皮卡丘现在教会了小狗勾怎么玩《牛牛》这个纸牌游戏U•ェ•*U。小狗勾通过在这个游戏上进行延申，发明了《狗勾》这个全新版本的游戏！
规则如下：

玩家每人发放 $n$ 张卡牌，每张牌的数字只有 $1$ 到 $1000$
玩家需要将手中的牌划分成两部分，每张牌要么属于第一部分，要么属于第二部分，玩家的目标是使得手中的牌型尽可能的大，谁的牌型更大谁就获胜
第一部分——【凑千】：牌的数字总和必须为 $1000$ 的正整数倍
第二部分——【凑牌型】：牌的数字总和对 $1000$ 取模得到的数字 $X$ 就是 $X$ 狗， $X$ 的数字大小体现了牌型大小
特殊的，对于第一部分，如果凑不出来 $1000$ 的正整数倍，就是没有狗，是最小的一种牌型
特殊的，对于第二部分，如果 $X=0$ ，并且凑的出来第一部分，这种情况称为狗勾，是最大的一种牌型
所以，牌型大小为：没有狗<一狗<二狗<三狗<…<九百九十八狗<九百九十九狗<狗勾

例如：
$[1,2,3]$ ，是没有狗
$[500,2,500]$ ，是二狗
$[500,500,1000]$ ，是狗勾
$[300,700]$ ，是狗勾

现在，小狗勾和皮卡丘正愉快地玩着这个全新版本的游戏……
只见小狗勾两手一挥，摊开他手中的所有牌，说自己凑成了狗勾这个牌型！
但皮卡丘怀疑他出老千。所以现在皮卡丘想知道，小狗勾手上真正能凑出的最大牌型的狗是什么，并输出凑成该牌型的方案

输入描述:

第一行包含一个整数 ，表示一共组测试数据
第二行包含一个整数，表示牌的数量
第三行包含个整数，表示牌上的数字

输出描述:

对于每组测试数据：
第一行输出一个整数，表示小狗勾他手上能凑出的最大牌型的狗是什么。如果为没有狗，请输出；否则，请输出，表示牌型大小，并且接下来第二行：
输出一个整数，表示对于第一部分【凑千】使用牌的数量，接下来该行输出个不同整数，表示每张牌所处的下标位置（下标从开始）
如果有多种方案凑成最大牌型的狗，输出任何一种即可
（注意：由于牛客存在输出限制不允许输出过多。若有狗，每组测试数据保证存在的构造方案，若输出过多你可能会得到【输出超限】的提交结果）

示例1

输入

复制

4
3
1 2 3
3
500 2 500
3
500 500 1000
2
300 700

输出

复制

说明

，是没有狗
，是二狗
，是狗勾
，是狗勾