QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#683380#6432. Puzzle in InazumaAndycraftAC ✓7ms4556kbC++204.2kb2024-10-27 20:38:352024-10-27 20:38:37

Judging History

你现在查看的是最新测评结果

  • [2024-10-27 20:38:37]
  • 评测
  • 测评结果:AC
  • 用时:7ms
  • 内存:4556kb
  • [2024-10-27 20:38:35]
  • 提交

answer

#include <cassert>
#include <iostream>
#include <algorithm>
#include <vector>
template <class T> using Arr = std::vector<T>;
typedef long long LL;
#if 1
#ifdef assert
#undef assert
#endif
#define assert(x) ({ if (!(x)) { printf("%s\n", #x); exit(0); } })
#endif

const int MAXN = 105;
int g[MAXN][MAXN], h[MAXN][MAXN];
int n;

void dfs(int now, int dep, const int &m, Arr<Arr<int>> &v) {
	static Arr<int> buf;
	if (dep == 4) {
		v.push_back(buf);
		return;
	}
	for (int i = now; i <= m; ++i) {
		buf.push_back(i);
		dfs(i + 1, dep + 1, m, v);
		buf.pop_back();
	}
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin >> n;
	LL sum = 0;
	for (int i = 1; i < n; ++i)
		for (int j = i + 1; j <= n; ++j) {
			std::cin >> g[i][j];
			g[j][i] = g[i][j];
			sum += g[i][j];
		}
	for (int i = 1; i < n; ++i)
		for (int j = i + 1; j <= n; ++j) {
			std::cin >> h[i][j];
			h[j][i] = h[i][j];
			sum -= h[i][j];
		}
	if (sum != 0)
		return puts("-1"), 0;
	Arr<Arr<int>> ans;
	auto act = [&](int a, int b, int c, int d, int x) {
		assert(a != b && a != c && a != d && b != c && b != d && c != d);
		ans.push_back({a, b, c, d, x});
		g[a][b] += x;
		g[a][c] += x;
		g[a][d] += x;
		g[b][c] -= x;
		g[c][d] -= x;
		g[b][d] -= x;

		g[b][a] += x;
		g[c][a] += x;
		g[d][a] += x;
		g[c][b] -= x;
		g[d][c] -= x;
		g[d][b] -= x;
	};
	auto mex = [&](Arr<int> v) { std::ranges::sort(v); v.erase(std::unique(v.begin(), v.end()), v.end()); for (int i = 0; i < (int)v.size(); ++i) if (v[i] != i) return i; return (int)v.size(); };
	auto cross_legacy = [&](int a, int b, int c, int d, int x) {
		assert(~x & 1);
		act(a, b, c, d, x / 2);
		act(b, a, c, d, x / 2);
	};
	auto cross = [&](int a, int b, int c, int d, int x) {
		assert(~x & 1);
		if (a != b && a != c && a != d && b != c && b != d && c != d)
			return cross_legacy(a, b, c, d, x), void();
		int u = mex({a - 1, b - 1, c - 1, d - 1}) + 1;
		int v = mex({a - 1, b - 1, c - 1, d - 1, u - 1}) + 1;
		cross_legacy(a, b, u, v, x);
		cross_legacy(u, v, c, d, x);
	};
	for (int i = n; i > 6; --i) {
		Arr<int> tp;
		for (int j = 1; j < i; ++j)
			if ((g[j][i] ^ h[j][i]) & 1)
				tp.push_back(j);
		int m = (int)tp.size();
		int j;
		for (j = 0; j + 3 <= m; j += 3)
			act(i, tp[j], tp[j + 1], tp[j + 2], 1);
		if (m == j + 1) {
			int u = mex({tp[j] - 1}) + 1;
			int v = mex({tp[j] - 1, u - 1}) + 1;
			int w = mex({tp[j] - 1, u - 1, v - 1}) + 1;
			act(i, tp[j], u, v, 1);
			act(i, tp[j], u, w, 1);
			act(i, tp[j], v, w, 1);
		} else if (m == j + 2) {
			int u = mex({tp[j] - 1, tp[j + 1] - 1}) + 1;
			int v = mex({tp[j] - 1, tp[j + 1] - 1, u - 1}) + 1;
			act(i, tp[j], u, v, 1);
			act(i, tp[j + 1], u, v, 1);
		} else
			assert(m == j);
	}

	int m = std::min(n, 6);
	Arr<Arr<int>> ch;
	dfs(1, 0, m, ch);
	int K = (int)ch.size();
	bool success = false;
	for (int S = 0; S < (1 << K); ++S) {
		for (int i = 0; i < K; ++i)
			if (S & (1 << i))
				for (int u = 0; u < 4; ++u)
					for (int v = u + 1; v < 4; ++v)
						g[ch[i][u]][ch[i][v]] ^= 1;

		bool fail = false;
		for (int i = 1; i < m; ++i)
			for (int j = i + 1; j <= m; ++j)
				if ((g[i][j] ^ h[i][j]) & 1) {
					fail = true;
					break;
				}
		for (int i = 0; i < K; ++i)
			if (S & (1 << i))
				for (int u = 0; u < 4; ++u)
					for (int v = u + 1; v < 4; ++v)
						g[ch[i][u]][ch[i][v]] ^= 1;
		if (!fail) {
			success = true;
			for (int i = 0; i < K; ++i)
				if (S & (1 << i))
					act(ch[i][0], ch[i][1], ch[i][2], ch[i][3], 1);
			break;
		}
	}
	if (!success)
		return puts("-1"), 0;
	for (int i = 1; i < n; ++i)
		for (int j = i + 1; j <= n; ++j)
			assert(~(g[i][j] ^ h[i][j]) & 1);
	if (n >= 5) {
		for (int i = n; i > 1; --i)
			for (int j = i - 1; j >= 1; --j)
				if (g[i][j] != h[i][j]) {
					assert(i != 2 || j != 1);
					int u = 1, v = 2;
					cross(i, j, u, v, h[i][j] - g[i][j]);
				}
	} else
		for (int i = n; i > 1; --i)
			for (int j = i - 1; j >= 1; --j)
				if (g[i][j] != h[i][j]) {
					// assert(i != 2 || j != 1);
					int u = mex({i - 1, j - 1}) + 1;
					int v = mex({i - 1, j - 1, u - 1}) + 1;
					cross_legacy(i, j, u, v, h[i][j] - g[i][j]);
				}
	// for (int i = 1; i < n; ++i)
	// 	for (int j = i + 1; j <= n; ++j)
	// 		assert(g[i][j] == h[i][j]);
	printf("%lu\n", ans.size());
	for (auto v : ans)
		printf("%d %d %d %d %d\n", v[0], v[1], v[2], v[3], v[4]);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3768kb

input:

4
0 1 1
0 0
1
1 0 0
1 1
0

output:

5
1 2 3 4 1
4 2 1 3 1
2 4 1 3 1
4 1 2 3 -1
1 4 2 3 -1

result:

ok n=4

Test #2:

score: 0
Accepted
time: 0ms
memory: 4032kb

input:

4
3 3 3
0 0
0
0 0 0
3 3
3

output:

7
1 2 3 4 1
4 3 1 2 2
3 4 1 2 2
4 2 1 3 2
2 4 1 3 2
4 1 2 3 -2
1 4 2 3 -2

result:

ok n=4

Test #3:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

5
-12 15 -12 1
37 14 7
7 9
-11
12 5 1 13
-1 -4 -7
-5 -9
18

output:

-1

result:

ok n=5

Test #4:

score: 0
Accepted
time: 0ms
memory: 3572kb

input:

4
37 81 -38
-79 -8
-42
20 -55 80
-23 -43
37

output:

-1

result:

ok n=4

Test #5:

score: 0
Accepted
time: 0ms
memory: 3832kb

input:

5
-22 63 -23 7
-11 36 66
66 -77
36
-87 -17 95 -65
-93 53 63
-54 -56
-77

output:

-1

result:

ok n=5

Test #6:

score: 0
Accepted
time: 0ms
memory: 3648kb

input:

6
-59 77 100 -28 -80
-14 -19 34 0
-8 34 44
58 38
7
87 -53 -57 -79 86
-19 -97 -51 -29
42 -14 61
-6 25
-24

output:

-1

result:

ok n=6

Test #7:

score: 0
Accepted
time: 0ms
memory: 3868kb

input:

10
96 -62 71 43 -41 62 37 -17 -73
-51 55 89 63 -17 81 98 78
-96 -70 -16 78 -63 49 86
20 -76 -21 8 -32 16
-93 45 -65 99 65
9 81 47 -2
-50 94 2
29 -77
77
67 -91 -97 -13 -75 -8 -79 21 -86
-44 -55 -92 19 -62 47 25 -88
-89 -10 1 94 -61 78 -70
8 30 -54 -9 19 -60
35 -21 -79 40 92
-56 -12 -56 2
-38 23 -31
2...

output:

-1

result:

ok n=10

Test #8:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

30
79 75 -71 -8 36 26 -38 -45 43 44 64 52 -23 -64 -73 97 -79 70 24 58 -9 11 14 58 -95 -88 -10 -80 -47
20 -55 86 89 -39 15 26 -32 38 -23 -30 -12 -4 81 39 -13 -43 -11 -38 -70 14 32 -67 -54 38 -80 -80 97
-49 -92 53 -94 -60 -77 -80 -11 75 51 43 52 -28 58 -26 71 -85 66 96 -61 52 -100 -49 93 92 -37 62
-55...

output:

-1

result:

ok n=30

Test #9:

score: 0
Accepted
time: 1ms
memory: 3616kb

input:

50
-47 49 10 46 -54 -70 -39 36 -1 100 -78 -27 23 43 15 -21 71 48 -82 95 85 -11 -99 35 -44 -31 70 -94 12 -45 -81 75 62 89 14 85 -82 -25 2 5 54 -25 -96 -30 -12 -70 13 -51 15
-48 -13 -53 49 19 -62 -15 -99 54 29 17 67 31 -58 80 -2 -97 -40 59 64 84 15 -32 76 -18 35 76 68 -69 47 51 -26 64 -70 71 14 -3 47 ...

output:

-1

result:

ok n=50

Test #10:

score: 0
Accepted
time: 1ms
memory: 3712kb

input:

100
-25 31 38 48 -19 32 87 -10 -30 -88 -79 98 -99 56 -52 -86 -89 51 77 -36 -52 72 -78 48 30 42 -45 84 -75 -71 -83 -48 92 -44 6 -83 -87 -82 -17 40 -44 82 64 -90 89 -34 88 10 -26 -84 -51 -29 86 -55 55 78 12 -38 -96 28 -78 52 -30 85 72 79 57 8 71 -68 -81 -21 14 44 -42 -26 42 95 20 -78 18 29 100 39 -19 ...

output:

-1

result:

ok n=100

Test #11:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

4
75 -69 93
78 24
-61
75 59 80
-50 31
-55

output:

-1

result:

ok n=4

Test #12:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

4
44 -25 -81
84 8
95
-70 -21 82
32 28
74

output:

-1

result:

ok n=4

Test #13:

score: 0
Accepted
time: 0ms
memory: 3840kb

input:

4
91 -18 -46
-80 -34
38
-25 18 -40
-35 86
-53

output:

-1

result:

ok n=4

Test #14:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

5
-16 92 -94 -83
-83 16 -74
75 3
-43
-28 45 -63 -100
-11 -39 -80
62 -14
21

output:

-1

result:

ok n=5

Test #15:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

5
-95 7 -3 76
57 -85 -98
-64 -28
70
5 48 -42 -99
-56 22 21
-51 74
-85

output:

-1

result:

ok n=5

Test #16:

score: 0
Accepted
time: 0ms
memory: 3608kb

input:

5
-10 31 33 -71
33 -49 4
72 -72
65
-74 55 20 41
61 62 -83
50 -1
-95

output:

-1

result:

ok n=5

Test #17:

score: 0
Accepted
time: 1ms
memory: 3780kb

input:

6
65 -33 2 -67 83
40 93 -28 86
54 -30 -11
56 40
-66
82 42 -32 -56 98
1 85 17 45
-12 -3 -50
-39 6
100

output:

49
1 2 3 5 1
1 2 3 6 1
1 2 4 5 1
1 3 4 5 1
2 3 4 5 1
6 5 1 2 83
5 6 1 2 83
6 4 1 2 -17
4 6 1 2 -17
6 3 1 2 -19
3 6 1 2 -19
6 2 3 4 -20
2 6 3 4 -20
3 4 1 2 -20
4 3 1 2 -20
6 1 3 4 7
1 6 3 4 7
3 4 1 2 7
4 3 1 2 7
5 4 1 2 -46
4 5 1 2 -46
5 3 1 2 15
3 5 1 2 15
5 2 3 4 23
2 5 3 4 23
3 4 1 2 23
4 3 1 2 23...

result:

ok n=6

Test #18:

score: 0
Accepted
time: 4ms
memory: 3784kb

input:

10
-68 -48 27 80 89 -22 -43 34 43
-41 -4 -10 -90 -62 -11 83 22
-64 -77 84 -20 -56 -56 -79
49 -54 90 19 75 6
41 6 -33 -29 -39
45 -27 7 6
-57 93 -53
-46 -85
-37
40 -49 -32 -28 -16 -71 -97 -99 -67
6 34 -65 -97 95 -99 72 -34
81 32 16 -49 -71 61 -83
89 -23 2 35 -20 50
-14 32 83 31 -43
-15 74 -87 22
-56 -...

output:

135
10 7 8 9 1
9 1 2 3 1
9 4 1 2 1
9 8 1 2 1
8 1 2 3 1
8 6 1 2 1
8 6 1 3 1
8 6 2 3 1
7 1 2 3 1
1 3 4 5 1
1 4 5 6 1
2 3 4 5 1
2 3 4 6 1
2 3 5 6 1
2 4 5 6 1
10 9 1 2 60
9 10 1 2 60
10 8 1 2 66
8 10 1 2 66
10 7 1 2 -3
7 10 1 2 -3
10 6 1 2 8
6 10 1 2 8
10 5 1 2 -2
5 10 1 2 -2
10 4 1 2 22
4 10 1 2 22
10 ...

result:

ok n=10

Test #19:

score: 0
Accepted
time: 1ms
memory: 3936kb

input:

30
-14 20 -41 -72 25 -17 -90 -2 12 -45 -13 -43 78 -3 15 -25 -5 43 38 -59 -20 -25 29 0 18 -54 49 -13 -88
87 -6 -53 -40 -13 6 -50 -38 -73 -15 95 88 -48 86 96 -63 -2 -49 -85 -19 -44 -11 -94 -51 -68 -71 -40 9
-11 -35 73 6 -10 -67 39 37 6 -3 81 -39 -89 -49 38 17 -25 2 11 -100 22 52 -39 -24 8 -78 13
51 81...

output:

1086
30 3 4 5 1
30 7 12 14 1
30 15 16 18 1
30 19 21 23 1
30 24 25 26 1
30 27 1 2 1
30 27 1 3 1
30 27 2 3 1
29 2 4 6 1
29 8 10 11 1
29 12 14 17 1
29 18 20 22 1
28 1 3 4 1
28 5 17 20 1
28 22 24 25 1
28 26 1 2 1
28 27 1 2 1
27 1 2 5 1
27 7 9 10 1
27 12 13 15 1
27 19 21 23 1
27 25 1 2 1
27 25 1 3 1
27 2...

result:

ok n=30

Test #20:

score: 0
Accepted
time: 2ms
memory: 4024kb

input:

50
-98 59 55 -73 49 29 73 -28 51 -81 77 88 -54 -2 58 6 17 -56 15 66 8 -86 96 -41 -33 93 84 4 -14 18 46 64 3 -73 -3 -65 49 30 35 -84 82 -66 93 83 -46 -42 95 -88 32
82 -2 -69 78 -69 -29 95 -25 -96 23 -78 -2 12 77 -79 65 13 17 69 14 91 82 43 -91 -25 6 8 17 -98 8 17 36 17 -80 91 -3 -35 -88 91 -89 80 25 ...

output:

2887
50 2 5 8 1
50 12 13 15 1
50 16 17 19 1
50 22 27 28 1
50 34 35 36 1
50 38 44 48 1
50 49 1 2 1
50 49 1 3 1
50 49 2 3 1
49 1 3 5 1
49 6 9 13 1
49 14 15 16 1
49 17 18 19 1
49 20 21 22 1
49 24 25 26 1
49 28 29 30 1
49 31 32 33 1
49 34 35 36 1
49 39 40 41 1
49 44 45 46 1
49 47 1 2 1
49 48 1 2 1
48 1 ...

result:

ok n=50

Test #21:

score: 0
Accepted
time: 7ms
memory: 4484kb

input:

100
-93 27 9 49 -69 -2 26 37 -10 -52 43 81 96 -10 32 46 -18 13 14 59 -58 3 -68 33 -62 -13 39 93 15 -81 -6 96 -81 -50 77 50 93 95 11 79 86 25 -28 48 77 5 -9 89 9 -62 86 -45 -50 70 -94 75 12 47 73 -26 -83 -29 -28 -70 -31 58 -67 63 47 9 -95 -52 94 -22 -96 -84 16 53 -14 -98 -11 26 -59 -28 -60 -80 -76 -2...

output:

11150
100 1 4 5 1
100 6 7 8 1
100 14 17 19 1
100 20 24 27 1
100 28 33 37 1
100 38 41 42 1
100 43 44 45 1
100 46 47 49 1
100 51 52 54 1
100 55 56 58 1
100 59 61 63 1
100 64 66 67 1
100 70 71 72 1
100 76 78 79 1
100 82 83 84 1
100 85 86 88 1
100 94 96 98 1
100 99 1 2 1
100 99 1 3 1
100 99 2 3 1
99 12 ...

result:

ok n=100

Test #22:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

4
63 -85 -96
73 -75
-24
-17 1 -24
-83 -8
-13

output:

-1

result:

ok n=4

Test #23:

score: 0
Accepted
time: 0ms
memory: 3840kb

input:

5
25 -22 24 37
-48 67 25
97 -55
57
-82 -44 -25 27
-35 89 81
88 37
71

output:

-1

result:

ok n=5

Test #24:

score: 0
Accepted
time: 1ms
memory: 3780kb

input:

6
-59 84 42 67 72
-51 -86 -37 -2
61 -84 -78
-8 -81
76
61 41 -3 32 -74
30 -39 -37 -13
-23 100 -24
-90 -41
-4

output:

50
1 2 3 5 1
1 2 3 6 1
1 2 4 5 1
1 2 4 6 1
1 3 4 5 1
2 3 4 6 1
6 5 1 2 -40
5 6 1 2 -40
6 4 1 2 21
4 6 1 2 21
6 3 1 2 28
3 6 1 2 28
6 2 3 4 -5
2 6 3 4 -5
3 4 1 2 -5
4 3 1 2 -5
6 1 3 4 -74
1 6 3 4 -74
3 4 1 2 -74
4 3 1 2 -74
5 4 1 2 -40
4 5 1 2 -40
5 3 1 2 93
3 5 1 2 93
5 2 3 4 1
2 5 3 4 1
3 4 1 2 1
4...

result:

ok n=6

Test #25:

score: 0
Accepted
time: 2ms
memory: 3836kb

input:

7
98 -77 33 -59 44 21
-71 -78 42 82 -60
6 76 96 -18
53 96 1
-72 -53
-86
69 40 -13 -11 63 55
-70 86 -49 -29 -34
-4 -51 67 19
-81 1 70
-77 10
13

output:

67
7 3 4 5 1
7 6 1 2 1
7 6 1 3 1
7 6 2 3 1
1 2 4 5 1
1 2 5 6 1
1 3 4 5 1
1 3 4 6 1
1 4 5 6 1
2 3 4 6 1
2 3 5 6 1
7 6 1 2 48
6 7 1 2 48
7 5 1 2 31
5 7 1 2 31
7 4 1 2 34
4 7 1 2 34
7 3 1 2 17
3 7 1 2 17
7 2 3 4 12
2 7 3 4 12
3 4 1 2 12
4 3 1 2 12
7 1 3 4 16
1 7 3 4 16
3 4 1 2 16
4 3 1 2 16
6 5 1 2 -1
...

result:

ok n=7

Test #26:

score: 0
Accepted
time: 2ms
memory: 3888kb

input:

37
1 -86 11 -63 -41 -21 99 14 28 17 63 66 24 53 2 -79 9 -95 -63 -40 12 -9 -71 90 -33 -13 -22 -36 50 31 -63 -1 7 -35 100 97
-57 -66 60 57 -30 8 32 -95 99 -67 -1 14 -75 83 42 -17 86 90 -33 -52 21 48 12 -69 -37 -25 74 -14 39 -20 65 38 14 -59 89
59 -3 91 76 -16 20 1 -85 51 -23 -24 49 10 -28 -11 -96 16 -...

output:

1596
37 3 5 8 1
37 12 13 14 1
37 17 22 24 1
37 25 26 28 1
37 29 33 34 1
37 35 1 2 1
37 36 1 2 1
36 1 5 7 1
36 8 11 12 1
36 13 14 16 1
36 17 18 21 1
36 22 23 24 1
36 25 29 31 1
36 33 1 2 1
36 33 1 3 1
36 33 2 3 1
35 2 3 5 1
35 10 13 17 1
35 19 21 22 1
35 28 29 30 1
35 31 32 33 1
34 7 8 10 1
34 15 16 ...

result:

ok n=37

Test #27:

score: 0
Accepted
time: 4ms
memory: 4112kb

input:

71
100 39 36 -14 -71 -95 1 23 -66 -23 58 46 83 67 16 95 -77 21 -87 20 69 -50 -74 -69 90 75 -18 84 -45 63 63 51 34 58 -51 90 -91 -50 -89 58 3 63 56 -58 -51 16 72 -36 36 64 -67 38 42 -93 76 -51 0 21 58 37 -4 26 -22 -12 72 93 -98 51 -11 -47
95 95 -17 -51 67 -38 63 74 52 89 80 -94 37 -18 -73 -32 -94 17 ...

output:

5700
71 1 5 6 1
71 10 11 12 1
71 15 18 20 1
71 25 26 27 1
71 28 29 31 1
71 32 34 35 1
71 39 41 42 1
71 45 47 48 1
71 51 53 54 1
71 56 57 58 1
71 64 65 66 1
71 69 1 2 1
71 69 1 3 1
71 69 2 3 1
70 1 3 6 1
70 7 8 9 1
70 11 17 18 1
70 22 28 32 1
70 33 34 36 1
70 38 39 40 1
70 42 43 44 1
70 45 46 47 1
70...

result:

ok n=71

Test #28:

score: 0
Accepted
time: 0ms
memory: 4160kb

input:

97
-73 49 60 15 -5 57 94 79 -7 51 -26 -21 -78 -67 31 90 7 46 -75 -82 3 24 -28 81 -77 -100 53 65 6 -63 17 100 13 -19 14 67 -31 7 92 45 61 58 -83 8 65 93 -35 94 97 97 80 -45 63 -15 57 -40 -65 -67 -32 12 -26 -99 32 -62 28 27 -25 52 -45 39 27 -34 78 65 -23 91 -71 -46 5 -36 84 -11 44 44 -74 -62 -91 -75 2...

output:

10484
97 4 7 9 1
97 14 16 18 1
97 19 20 21 1
97 22 25 28 1
97 29 30 32 1
97 33 35 36 1
97 37 38 43 1
97 47 49 50 1
97 51 52 56 1
97 58 60 64 1
97 66 70 71 1
97 72 73 79 1
97 81 84 88 1
97 89 90 93 1
97 94 95 96 1
96 3 6 7 1
96 9 10 14 1
96 15 20 22 1
96 24 25 27 1
96 28 29 31 1
96 32 33 36 1
96 38 3...

result:

ok n=97

Test #29:

score: 0
Accepted
time: 2ms
memory: 4324kb

input:

59
-83 56 51 -64 30 35 52 -22 -54 -36 76 25 37 39 -26 -10 2 -99 71 95 -67 -2 33 9 -79 97 -18 -56 -54 99 -2 -3 -64 -42 -72 81 -84 5 -39 93 -72 -90 19 4 95 -30 28 -1 -81 -59 47 15 -94 -59 87 0 82 26
42 76 56 47 -5 26 -76 85 -16 -16 68 -19 26 -93 0 24 -47 20 16 -63 75 -36 -2 -88 38 -14 -70 27 -98 -70 4...

output:

3975
59 2 6 7 1
59 8 9 10 1
59 11 15 19 1
59 20 23 28 1
59 34 36 39 1
59 40 43 45 1
59 54 55 57 1
58 1 2 3 1
58 5 12 13 1
58 15 16 17 1
58 21 22 23 1
58 25 26 31 1
58 33 35 36 1
58 38 39 40 1
58 41 42 43 1
58 46 54 55 1
58 56 1 2 1
58 56 1 3 1
58 56 2 3 1
57 3 6 7 1
57 8 9 11 1
57 12 16 20 1
57 21 2...

result:

ok n=59

Test #30:

score: 0
Accepted
time: 3ms
memory: 4248kb

input:

100
33 54 -87 -27 79 -67 -64 29 -32 49 -43 87 29 -64 38 -27 47 -67 -57 -66 -84 -67 68 -34 -12 -50 -55 -75 -96 0 71 -49 46 -39 63 -48 -60 -53 -92 18 -33 51 1 47 -100 42 81 -40 -14 43 -51 -7 -77 30 -20 -93 -99 -70 26 52 -58 -74 57 -54 -3 93 58 -90 32 -100 -72 51 -93 48 19 84 -89 77 55 12 -45 -5 39 5 -...

output:

11143
100 2 3 6 1
100 7 12 16 1
100 18 21 23 1
100 25 27 29 1
100 31 32 34 1
100 35 36 37 1
100 38 39 40 1
100 42 44 47 1
100 49 50 53 1
100 55 57 58 1
100 59 61 62 1
100 66 67 69 1
100 73 77 81 1
100 82 83 87 1
100 88 89 90 1
100 92 93 94 1
100 95 96 98 1
100 99 1 2 1
100 99 1 3 1
100 99 2 3 1
99 3...

result:

ok n=100

Test #31:

score: 0
Accepted
time: 5ms
memory: 4556kb

input:

100
68 -49 44 23 8 57 17 32 21 46 43 -84 -62 63 -83 99 -63 59 -11 31 83 -62 -24 66 -50 81 30 -55 -7 -82 68 73 -31 -33 -65 -91 -70 -68 73 50 -87 86 58 14 8 -24 31 37 66 -46 38 -64 -79 13 15 88 -29 29 -84 0 -10 -75 -100 -26 -50 -38 36 -35 85 48 58 -98 5 63 40 -61 93 -52 -37 16 -6 72 -77 -83 -87 50 -20...

output:

11163
100 2 5 8 1
100 12 13 16 1
100 17 19 20 1
100 24 27 28 1
100 29 32 38 1
100 40 41 46 1
100 49 54 55 1
100 58 60 61 1
100 66 67 69 1
100 73 76 77 1
100 79 80 81 1
100 82 85 86 1
100 87 93 94 1
100 95 1 2 1
100 99 1 2 1
99 1 2 4 1
99 5 6 8 1
99 9 11 12 1
99 14 15 16 1
99 17 18 19 1
99 23 25 27 1...

result:

ok n=100

Test #32:

score: 0
Accepted
time: 6ms
memory: 4556kb

input:

100
-54 27 -16 97 15 -92 -66 73 -13 12 44 -10 -47 95 -25 -67 21 73 -19 -7 96 1 98 66 -58 16 -49 26 9 -97 90 -58 -17 -26 69 1 -37 -40 33 -36 14 -74 -44 -83 -44 66 -52 -11 95 -66 46 -72 37 67 28 40 -63 37 -24 -29 24 28 41 2 -41 71 -29 25 26 93 59 11 -66 -60 70 24 -42 -65 79 -56 -24 77 23 51 -19 25 9 3...

output:

11149
100 1 2 3 1
100 7 8 9 1
100 10 11 15 1
100 17 18 19 1
100 20 21 27 1
100 29 30 32 1
100 34 37 38 1
100 39 41 42 1
100 43 45 46 1
100 49 50 52 1
100 56 57 58 1
100 61 63 64 1
100 66 68 69 1
100 74 78 79 1
100 80 83 85 1
100 88 90 92 1
100 93 95 96 1
100 98 1 2 1
100 99 1 2 1
99 7 12 14 1
99 16 ...

result:

ok n=100

Test #33:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

5
96 70 0 -25
3 10 -61
-40 8
58
62 43 24 82
-81 -49 68
88 -20
-98

output:

-1

result:

ok n=5

Test #34:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

5
43 -6 -77 19
84 1 -9
-87 67
-68
-42 -48 77 65
17 -1 -86
-22 -42
49

output:

-1

result:

ok n=5

Test #35:

score: 0
Accepted
time: 0ms
memory: 3804kb

input:

5
-85 -81 -99 97
10 -58 -26
-7 48
1
71 -68 -86 -65
84 41 -74
-84 41
-60

output:

-1

result:

ok n=5

Test #36:

score: 0
Accepted
time: 0ms
memory: 3868kb

input:

5
-59 -76 -34 15
-16 76 -35
82 -35
-41
-70 -91 31 82
94 -50 -1
8 -37
-89

output:

32
1 2 3 4 1
1 2 3 5 1
1 2 4 5 1
1 3 4 5 1
5 4 1 2 -23
4 5 1 2 -23
5 2 3 4 18
2 5 3 4 18
3 4 1 2 18
4 3 1 2 18
5 1 3 4 32
1 5 3 4 32
3 4 1 2 32
4 3 1 2 32
4 3 1 2 -36
3 4 1 2 -36
4 2 3 5 -62
2 4 3 5 -62
3 5 1 2 -62
5 3 1 2 -62
4 1 3 5 31
1 4 3 5 31
3 5 1 2 31
5 3 1 2 31
3 2 4 5 56
2 3 4 5 56
4 5 1 2...

result:

ok n=5

Test #37:

score: 0
Accepted
time: 0ms
memory: 3676kb

input:

4
-52 -78 -9
100 30
51
14 62 -52
86 -86
18

output:

-1

result:

ok n=4

Test #38:

score: 0
Accepted
time: 0ms
memory: 3840kb

input:

4
-74 73 69
-54 -65
44
59 -50 -46
32 -49
47

output:

-1

result:

ok n=4

Test #39:

score: 0
Accepted
time: 6ms
memory: 4456kb

input:

100
-61 -13 42 41 82 78 99 70 15 -38 76 -21 80 27 9 33 77 -15 -58 -80 -32 -8 52 -53 56 -86 -79 19 -26 -74 68 -92 61 9 2 -65 -92 47 -81 53 65 92 27 -84 94 -78 29 -61 27 68 91 -18 -95 64 67 -73 77 23 -77 -87 84 66 -84 -14 27 -64 -27 -74 -65 74 -65 69 -23 -75 -70 -77 -26 61 -23 47 -20 -5 1 -1 38 97 26 ...

output:

11182
100 1 2 3 1
100 7 8 10 1
100 12 13 14 1
100 15 21 23 1
100 31 32 36 1
100 37 40 41 1
100 43 44 46 1
100 47 49 52 1
100 54 56 58 1
100 64 66 67 1
100 68 69 72 1
100 75 76 77 1
100 78 79 80 1
100 82 87 92 1
100 93 94 95 1
100 97 98 99 1
99 2 3 9 1
99 10 12 14 1
99 15 16 18 1
99 19 21 22 1
99 24 ...

result:

ok n=100

Test #40:

score: 0
Accepted
time: 3ms
memory: 4228kb

input:

100
-80 84 40 30 -73 76 -79 9 32 -61 86 -44 13 -8 -97 -85 -9 76 75 85 -2 -22 25 58 -37 4 -86 64 -89 25 14 32 11 -71 -62 -55 -78 19 -54 -2 12 56 -78 33 74 1 -98 -1 -41 19 71 0 24 -5 -59 -92 78 62 -84 59 75 95 -27 22 -88 77 50 80 25 -77 29 -28 -34 -98 81 43 -91 -31 21 100 31 -96 -5 -51 -1 80 -23 9 15 ...

output:

11155
100 2 4 5 1
100 6 7 9 1
100 10 11 13 1
100 16 17 20 1
100 22 23 24 1
100 26 27 28 1
100 30 32 33 1
100 34 35 36 1
100 38 39 40 1
100 42 47 52 1
100 53 55 56 1
100 57 58 59 1
100 62 63 64 1
100 65 66 68 1
100 70 71 72 1
100 73 74 75 1
100 76 81 82 1
100 84 85 86 1
100 87 90 91 1
100 93 94 95 1
...

result:

ok n=100

Test #41:

score: 0
Accepted
time: 0ms
memory: 3736kb

input:

4
40 -37 6
-68 -33
100
43 28 9
-71 -98
97

output:

7
1 2 3 4 1
4 3 1 2 -1
3 4 1 2 -1
4 2 1 3 -32
2 4 1 3 -32
4 1 2 3 1
1 4 2 3 1

result:

ok n=4

Test #42:

score: 0
Accepted
time: 0ms
memory: 3764kb

input:

4
84 -41 68
30 -18
19
73 -64 21
77 5
30

output:

7
1 2 3 4 1
4 3 1 2 6
3 4 1 2 6
4 2 1 3 12
2 4 1 3 12
4 1 2 3 -24
1 4 2 3 -24

result:

ok n=4

Test #43:

score: 0
Accepted
time: 0ms
memory: 3828kb

input:

4
27 -78 29
81 -14
-44
41 -62 33
77 -30
-58

output:

6
4 3 1 2 -7
3 4 1 2 -7
4 2 1 3 -8
2 4 1 3 -8
4 1 2 3 2
1 4 2 3 2

result:

ok n=4

Test #44:

score: 0
Accepted
time: 0ms
memory: 3768kb

input:

4
-82 85 8
1 -50
-10
-41 50 47
-38 -15
-51

output:

7
1 2 3 4 1
4 3 1 2 -20
3 4 1 2 -20
4 2 1 3 18
2 4 1 3 18
4 1 2 3 19
1 4 2 3 19

result:

ok n=4

Test #45:

score: 0
Accepted
time: 0ms
memory: 3772kb

input:

4
-39 -81 59
-49 52
-66
-32 -74 24
-14 45
-73

output:

7
1 2 3 4 1
4 3 1 2 -3
3 4 1 2 -3
4 2 1 3 -3
2 4 1 3 -3
4 1 2 3 -18
1 4 2 3 -18

result:

ok n=4

Test #46:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

4
6 6 6
6 6
6
2 2 2
2 2
2

output:

-1

result:

ok n=4

Test #47:

score: 0
Accepted
time: 0ms
memory: 3544kb

input:

5
6 6 6 6
6 6 6
6 6
6
2 2 2 2
2 2 2
2 2
2

output:

-1

result:

ok n=5

Test #48:

score: 0
Accepted
time: 0ms
memory: 3768kb

input:

5
-21 -29 -2 -46
-55 78 43
87 -33
18
-55 55 -78 -8
-38 -25 60
50 16
63

output:

31
2 3 4 5 1
5 4 1 2 23
4 5 1 2 23
5 3 1 2 25
3 5 1 2 25
5 2 3 4 8
2 5 3 4 8
3 4 1 2 8
4 3 1 2 8
5 1 3 4 19
1 5 3 4 19
3 4 1 2 19
4 3 1 2 19
4 3 1 2 -18
3 4 1 2 -18
4 2 3 5 -52
2 4 3 5 -52
3 5 1 2 -52
5 3 1 2 -52
4 1 3 5 -38
1 4 3 5 -38
3 5 1 2 -38
5 3 1 2 -38
3 2 4 5 8
2 3 4 5 8
4 5 1 2 8
5 4 1 2 8...

result:

ok n=5

Test #49:

score: 0
Accepted
time: 0ms
memory: 3768kb

input:

5
95 -11 -61 61
85 -32 -14
-12 -75
-89
-42 -14 -23 40
-79 91 -90
19 -19
64

output:

32
1 2 3 5 1
2 3 4 5 1
5 4 1 2 77
4 5 1 2 77
5 3 1 2 29
3 5 1 2 29
5 2 3 4 -38
2 5 3 4 -38
3 4 1 2 -38
4 3 1 2 -38
5 1 3 4 -11
1 5 3 4 -11
3 4 1 2 -11
4 3 1 2 -11
4 3 1 2 16
3 4 1 2 16
4 2 3 5 61
2 4 3 5 61
3 5 1 2 61
5 3 1 2 61
4 1 3 5 19
1 4 3 5 19
3 5 1 2 19
5 3 1 2 19
3 2 4 5 -82
2 3 4 5 -82
4 5...

result:

ok n=5

Test #50:

score: 0
Accepted
time: 0ms
memory: 3784kb

input:

5
30 12 46 66
-22 -53 -8
63 -40
-84
36 38 36 55
-63 -22 2
28 -4
-96

output:

33
1 2 3 5 1
1 2 4 5 1
1 3 4 5 1
5 4 1 2 -5
4 5 1 2 -5
5 3 1 2 19
3 5 1 2 19
5 2 3 4 6
2 5 3 4 6
3 4 1 2 6
4 3 1 2 6
5 1 3 4 -7
1 5 3 4 -7
3 4 1 2 -7
4 3 1 2 -7
4 3 1 2 -17
3 4 1 2 -17
4 2 3 5 16
2 4 3 5 16
3 5 1 2 16
5 3 1 2 16
4 1 3 5 -6
1 4 3 5 -6
3 5 1 2 -6
5 3 1 2 -6
3 2 4 5 -20
2 3 4 5 -20
4 5...

result:

ok n=5

Test #51:

score: 0
Accepted
time: 0ms
memory: 3776kb

input:

5
-89 -74 46 -19
59 46 45
-15 -35
-12
-35 -87 -5 28
15 76 37
-22 -56
1

output:

31
1 3 4 5 1
5 4 1 2 7
4 5 1 2 7
5 3 1 2 -10
3 5 1 2 -10
5 2 3 4 -4
2 5 3 4 -4
3 4 1 2 -4
4 3 1 2 -4
5 1 3 4 23
1 5 3 4 23
3 4 1 2 23
4 3 1 2 23
4 3 1 2 -3
3 4 1 2 -3
4 2 3 5 15
2 4 3 5 15
3 5 1 2 15
5 3 1 2 15
4 1 3 5 -26
1 4 3 5 -26
3 5 1 2 -26
5 3 1 2 -26
3 2 4 5 -22
2 3 4 5 -22
4 5 1 2 -22
5 4 1...

result:

ok n=5

Test #52:

score: 0
Accepted
time: 0ms
memory: 4032kb

input:

5
-91 -64 -43 -21
-48 11 -46
-58 43
-43
-52 -87 -45 -79
-35 57 -58
-18 -5
-38

output:

33
1 2 4 5 1
1 3 4 5 1
2 3 4 5 1
5 4 1 2 4
4 5 1 2 4
5 3 1 2 -23
3 5 1 2 -23
5 2 3 4 -6
2 5 3 4 -6
3 4 1 2 -6
4 3 1 2 -6
5 1 3 4 -30
1 5 3 4 -30
3 4 1 2 -30
4 3 1 2 -30
4 3 1 2 21
3 4 1 2 21
4 2 3 5 23
2 4 3 5 23
3 5 1 2 23
5 3 1 2 23
4 1 3 5 -2
1 4 3 5 -2
3 5 1 2 -2
5 3 1 2 -2
3 2 4 5 6
2 3 4 5 6
4...

result:

ok n=5

Test #53:

score: 0
Accepted
time: 0ms
memory: 4028kb

input:

5
-18 70 -27 11
54 -19 36
-94 85
-52
9 41 -28 35
-3 -12 36
-39 75
-68

output:

27
1 2 3 4 1
5 4 1 2 -8
4 5 1 2 -8
5 3 1 2 -5
3 5 1 2 -5
5 1 3 4 12
1 5 3 4 12
3 4 1 2 12
4 3 1 2 12
4 3 1 2 28
3 4 1 2 28
4 2 3 5 4
2 4 3 5 4
3 5 1 2 4
5 3 1 2 4
4 1 3 5 -1
1 4 3 5 -1
3 5 1 2 -1
5 3 1 2 -1
3 2 4 5 -28
2 3 4 5 -28
4 5 1 2 -28
5 4 1 2 -28
3 1 4 5 -15
1 3 4 5 -15
4 5 1 2 -15
5 4 1 2 -15

result:

ok n=5

Test #54:

score: 0
Accepted
time: 0ms
memory: 3772kb

input:

5
30 69 -94 16
75 32 49
59 31
26
71 26 -82 13
26 80 18
89 30
22

output:

29
1 2 3 5 1
5 4 1 2 -2
4 5 1 2 -2
5 2 3 4 -15
2 5 3 4 -15
3 4 1 2 -15
4 3 1 2 -15
5 1 3 4 -2
1 5 3 4 -2
3 4 1 2 -2
4 3 1 2 -2
4 3 1 2 15
3 4 1 2 15
4 2 3 5 24
2 4 3 5 24
3 5 1 2 24
5 3 1 2 24
4 1 3 5 6
1 4 3 5 6
3 5 1 2 6
5 3 1 2 6
3 2 4 5 -24
2 3 4 5 -24
4 5 1 2 -24
5 4 1 2 -24
3 1 4 5 -22
1 3 4 5...

result:

ok n=5

Test #55:

score: 0
Accepted
time: 0ms
memory: 4064kb

input:

5
84 -23 38 82
-1 3 32
-72 -40
-95
98 -5 -13 87
34 -25 38
-60 -100
-46

output:

33
1 2 3 4 1
1 2 3 5 1
2 3 4 5 1
5 4 1 2 25
4 5 1 2 25
5 3 1 2 -29
3 5 1 2 -29
5 2 3 4 3
2 5 3 4 3
3 4 1 2 3
4 3 1 2 3
5 1 3 4 2
1 5 3 4 2
3 4 1 2 2
4 3 1 2 2
4 3 1 2 7
3 4 1 2 7
4 2 3 5 -14
2 4 3 5 -14
3 5 1 2 -14
5 3 1 2 -14
4 1 3 5 -26
1 4 3 5 -26
3 5 1 2 -26
5 3 1 2 -26
3 2 4 5 18
2 3 4 5 18
4 5...

result:

ok n=5

Test #56:

score: 0
Accepted
time: 0ms
memory: 3776kb

input:

5
-56 48 23 92
-37 53 -18
-30 -28
-34
-57 99 0 89
-68 64 19
-85 -19
-29

output:

35
1 2 3 4 1
1 2 3 5 1
1 2 4 5 1
1 3 4 5 1
2 3 4 5 1
5 4 1 2 4
4 5 1 2 4
5 3 1 2 6
3 5 1 2 6
5 2 3 4 19
2 5 3 4 19
3 4 1 2 19
4 3 1 2 19
5 1 3 4 -3
1 5 3 4 -3
3 4 1 2 -3
4 3 1 2 -3
4 3 1 2 -26
3 4 1 2 -26
4 2 3 5 6
2 4 3 5 6
3 5 1 2 6
5 3 1 2 6
4 1 3 5 -13
1 4 3 5 -13
3 5 1 2 -13
5 3 1 2 -13
3 2 4 5...

result:

ok n=5

Test #57:

score: 0
Accepted
time: 0ms
memory: 3832kb

input:

4
0 0 0
0 0
0
0 0 0
0 0
0

output:

0

result:

ok n=4