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
#include <iostream>

using namespace std;

int main(){
	
	int t;
	cin >> t;
	for(; t > 0; --t){
		int n, m;
		
		cin >> n;
		int fib1[n];
		for(int i = 0; i < n; ++i){
			cin >> fib1[i];
		}
		
		cin >> m;
		int fib2[m];
		for(int i = 0; i < m; ++i){
			cin >> fib2[i];
		}
		
		long long f1 = 0, f2 = 0;
		long long a = 1, b = 1, c = 1;
		
		if(n < m){
			int i = 0;
			for(; i < n; ++i){
				if(fib1[i]) f1 += c;
				if(fib2[i]) f2 += c;
				a = b;
				b = c;
				c = a + b;
			}
			for(; i < m; ++i){
				if(fib2[i]) f2 += c;
				a = b;
				b = c;
				c = a + b;
			}
		}else{
			int i = 0;
			for(; i < m; ++i){
				if(fib1[i]) f1 += c;
				if(fib2[i]) f2 += c;
				a = b;
				b = c;
				c = a + b;
			}
			for(; i < n; ++i){
				if(fib1[i]) f1 += c;
				a = b;
				b = c;
				c = a + b;
			}
		}
		
		long long result = f1 * f2;
		n = 1;
		a = 1; b = 1; c = 1;
		if(c <= result) n = 0;
		while(c <= result){
			a = b;
			b = c;
			c = a + b;
			n++;
		}
		
		int resArr[n];
		if(result == 0) resArr[n - 1] = 0;
		else resArr[n - 1] = 1;
		result -= b;
		c = b;
		b = a;
		a = c - b;
		
		for(int i = n - 2; i >= 0; --i){
			if(b <= result){
				resArr[i] = 1;
				result -= b;
			}else{
				resArr[i] = 0;
			}
			c = b;
			b = a;
			a = c - b;
		}
		
		cout << n;
		for(int i = 0; i < n; ++i){
			cout << ' ' << resArr[i];
		}
		cout << endl;
	}
	
	return 0;
}