#P18245. A + B = C Problem

A + B = C Problem

A + B = C Problem

题目描述

给定三个正整数 pA,pB,pCp_A,p_B,p_C。请构造三个无限长的二进制字符串 A,B,CA,B,C,使它们的周期分别为 pA,pB,pCp_A,p_B,p_C,并满足

A⊕B=C.A\oplus B=C.

如果无法构造,输出无解。

这里,字符串的周期是使 si=si+ks_i=s_{i+k} 对所有 i≥1i\ge1 都成立的最小正整数 kk。

两个无限二进制字符串的异或按位定义,即 (s⊕t)i=si⊕ti(s\oplus t)_i=s_i\oplus t_i。

输入格式

第一行包含整数 TT,表示测试数据组数。

每组数据一行,包含三个整数 pA,pB,pCp_A,p_B,p_C。

输出格式

对每组数据:

  • 如果无解,输出一行 NO。
  • 否则,先输出一行 YES,再输出三行二进制字符串,长度分别为 pA,pB,pCp_A,p_B,p_C,表示所构造的无限字符串 A,B,CA,B,C 的前 pA,pB,pCp_A,p_B,p_C 位。每个无限字符串由对应的有限字符串不断重复得到。

YES 和 NO 的字母大小写均可。若有多种合法方案,输出任意一种。

数据范围

  • 1≤T≤1041\le T\le10^4。
  • 1≤pA,pB,pC≤1061\le p_A,p_B,p_C\le10^6。
  • 一个输入文件中,所有测试数据的 max⁡(pA,pB,pC)\max(p_A,p_B,p_C) 之和不超过 10610^6。

样例

2
2 3 6
2 3 5
YES
01
011
001110
NO