1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 #include #define FOR(i, a, b) for (int i=(a); i<(int)(b); i++) #define PPC(x) __builtin_popcount(x) #define pb push_back #define ALL(x) (x).begin(), (x).end() #define st first #define nd second using namespace std; const int maxN = 1 << 24, maxF = 92; vector out; int in[2][maxN]; long long F[maxF]; void print() { printf("%d ", (int)out.size()); for (int v : out) printf("%d ", v); printf("\n"); } void printFibProd(int i, int j) { if (j < i) swap(i, j); int shift = j-i; if (i % 2 == 0) shift = max(0, shift-1); assert(shift >= 0); FOR(_, 0, shift) out.pb(0); out.pb(1); int ile = i/2; if (i % 2 == 0) { if (j != i) out.pb(0); out.pb(0), out.pb(1); ile--; } assert(ile >= 0); while (ile--) out.pb(0), out.pb(0), out.pb(0), out.pb(1); print(); } bool tryBrut(int a, int b) { long long v[2] = {0ll, 0ll}; int n[2] = {a, b}; FOR(s, 0, 2) { if (n[s] >= maxF) return false; FOR(i, 1, n[s]+1) if (in[s][i]) { if (v[s] > LLONG_MAX - F[i]) return false; v[s] += F[i]; } } if (v[0] > LLONG_MAX / v[1]) return false; long long w = v[0] * v[1]; for (int i = maxF-1; i>0; i--) { if (F[i] <= w) w -= F[i], out.pb(1); else out.pb(0); } reverse(ALL(out)); while (out.back() == 0) out.pop_back(); print(); return true; } void solve() { int n[2], w[2]; FOR(s, 0, 2) { w[s] = 0; scanf ("%d", n+s); FOR(i, 1, n[s]+1) scanf ("%d", &in[s][i]), w[s] += in[s][i]; } out.resize(0); if (w[0] == 1 and w[1] == 1) { printFibProd(n[0], n[1]); return; } if (tryBrut(n[0], n[1])) return; } int main() { F[0] = F[1] = 1ll; FOR(i, 2, maxF) F[i] = F[i-2] + F[i-1]; int t; scanf ("%d", &t); while (t--) solve(); return 0; }