#P4505. [AMPPZ2014]Hit of the Season

    ID: 2777 传统题 2000ms 256MiB 尝试: 73 已通过: 25 难度: 7 上传者: 标签>难度分类提高+/省选-枚举与搜索回溯搜索可行性剪枝构造与建模对称性分析数据结构阈值划分大小情况模拟与实现技巧增量维护CF2300

[AMPPZ2014]Hit of the Season

[AMPPZ 2014] Hit of the Season

题目描述

Byteotia 印刷厂接到了一批条纹壁纸的订单。每张壁纸有 nn 条等宽的竖条,可以印成红、绿、蓝三种颜色。客户指定了其中一些条纹的颜色,其余条纹由印刷厂决定。

印刷厂使用同一块模板多次印刷。模板由若干条颜色固定的连续条纹组成。每次印刷时,把整块模板与壁纸上同样数量的连续条纹对齐,模板的每一条都必须落在壁纸内。模板的方向固定,每次使用时都不能旋转或反转。

一条条纹可以印刷多次。如果印上不同的颜色,它最终会呈现混合色。客户指定颜色的条纹必须保持纯色,因此每一次覆盖该处的印刷都必须使用客户指定的颜色。其余位置允许出现混合色。每条条纹至少要被印刷一次。

给出客户的要求,求一块能完成印刷的最短模板。

输入格式

第一行输入一个整数 tt,表示数据组数,满足 1≤t≤101\le t\le 10。

接下来 tt 行,每行一个字符串 SS。字符 R、G、B 分别表示红、绿、蓝色,* 表示未指定颜色。1≤∣S∣≤30001\le |S|\le 3000,每个字符串至多含 1919 个星号。

输出格式

对于每组数据,输出一行只含 R、G、B 的字符串,表示一块最短模板。若有多个最短模板,输出任意一种。

样例

1
RRG*R*BRR**B
RRGB