友情提示:380元/半年,儿童学编程,就上码丁实验室。
【题目描述】
给出一个只有数字、逗号和问号组成的字符串,其中问号表示这个字符未知,你需要尝试还原出这个字符串,使得这个字符串合法且字典序最小(逗号的字典序比数字小)。
一个合法的字符串要满足以下4个条件:
(1) 仅包含数字和逗号;
(2) 相邻数字用逗号隔开,但串首和串尾不能有逗号;
(3) 所有数字都是正整数,没有前导0;
(4) 数字序列严格递增。
【输入】
第一行一个正整数$T$,表示数据组数。
接下来$T$行,每行一个字符串$S$,表示需要还原的字符串。
【输出】
对于每组数据,输出还原后的串。如果无解,输出“$impossible$”(不含引号)。
【输入样例】
5 ?? ??? ?????????,9 ?,10,?????????????????,16,?? ?2?5??7?,??
【输出样例】
10 1,2 1,2,3,4,5,9 impossible 12,50,70,71
【提示】
【数据规模与约定】
对于40%的数据,保证问号不超过$10$个。
对于100%的数据,$1≤T≤10,1≤len(S)≤50$。