#P4505. [AMPPZ2014]Hit of the Season
[AMPPZ2014]Hit of the Season
[AMPPZ 2014] Hit of the Season
题目描述
Byteotia 印刷厂接到了一批条纹壁纸的订单。每张壁纸有 条等宽的竖条,可以印成红、绿、蓝三种颜色。客户指定了其中一些条纹的颜色,其余条纹由印刷厂决定。
印刷厂使用同一块模板多次印刷。模板由若干条颜色固定的连续条纹组成。每次印刷时,把整块模板与壁纸上同样数量的连续条纹对齐,模板的每一条都必须落在壁纸内。模板的方向固定,每次使用时都不能旋转或反转。
一条条纹可以印刷多次。如果印上不同的颜色,它最终会呈现混合色。客户指定颜色的条纹必须保持纯色,因此每一次覆盖该处的印刷都必须使用客户指定的颜色。其余位置允许出现混合色。每条条纹至少要被印刷一次。
给出客户的要求,求一块能完成印刷的最短模板。
输入格式
第一行输入一个整数 ,表示数据组数,满足 。
接下来 行,每行一个字符串 。字符 R、G、B 分别表示红、绿、蓝色,* 表示未指定颜色。,每个字符串至多含 个星号。
输出格式
对于每组数据,输出一行只含 R、G、B 的字符串,表示一块最短模板。若有多个最短模板,输出任意一种。
样例
1
RRG*R*BRR**B
RRGB