Tập lũy thừa của một tập \(S\) là tập hợp tất cả các tập con của \(S\), bao gồm tập rỗng và chính \(S\). Đi từ một tập đến tập lũy thừa của nó thì dễ, nhưng trong bài này ta sẽ đi theo chiều ngược lại!

Ta bắt đầu với một tập các số nguyên \(S\) mà các phần tử không nhất thiết phân biệt, tìm tập lũy thừa của nó, rồi thay mỗi phần tử của tập lũy thừa (tức mỗi tập con) bằng tổng các phần tử trong tập con đó để tạo ra một tập mới \(S'\). Ví dụ, nếu \(S=\{-1,1\}\) thì tập lũy thừa là \(\{\{\},\{-1\},\{1\},\{-1,1\}\}\), nên \(S'=\{0,-1,1,0\}\). \(S'\) được phép chứa phần tử trùng nhau; vì vậy nếu \(S\) có \(N\) phần tử thì \(S'\) luôn có đúng \(2^N\) phần tử.

Cho mô tả các phần tử của \(S'\) và tần suất của chúng, hãy xác định tập \(S\) ban đầu. Đề bảo đảm tồn tại \(S\). Nếu có nhiều tập \(S\) có thể tạo ra \(S'\), đề bảo đảm tập ban đầu là tập sớm nhất trong số đó. Để so sánh hai tập khác nhau \(S_1\) và \(S_2\) có cùng số phần tử, hãy sắp xếp mỗi tập theo thứ tự không giảm rồi xét vị trí đầu tiên từ trái sang mà chúng khác nhau. \(S_1\) sớm hơn khi và chỉ khi phần tử tại vị trí đó trong \(S_1\) nhỏ hơn phần tử tương ứng trong \(S_2\).

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test gồm một dòng chứa số nguyên \(P\), sau đó là hai dòng, mỗi dòng chứa \(P\) số nguyên cách nhau bởi dấu cách. Dòng đầu trong hai dòng này chứa tất cả các giá trị khác nhau \(E_1,E_2,\ldots,E_P\) xuất hiện trong \(S'\), được sắp xếp tăng dần. Dòng thứ hai chứa các tần suất \(F_1,F_2,\ldots,F_P\). Nói cách khác, với mọi \(i\), giá trị \(E_i\) xuất hiện đúng \(F_i\) lần trong \(S'\).

Dữ liệu ra

Với mỗi bộ test, in một dòng bắt đầu bằng Case #x:, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ 1), rồi in các phần tử của tập \(S\) ban đầu, cách nhau bởi dấu cách và theo thứ tự không giảm. Bạn phải liệt kê trực tiếp các phần tử của \(S\), không dùng hai danh sách giá trị và tần suất như cách dữ liệu vào mô tả \(S'\).

Ràng buộc

• \(1\le T\le100\).
• \(1\le P\le10000\).
• \(F_i\ge1\).

Phân nhóm

• Tập nhỏ: \(S\) có từ 1 đến 20 phần tử; \(0\le E_i\le10^8\).
• Tập lớn: \(S\) có từ 1 đến 60 phần tử; \(-10^{10}\le E_i\le10^{10}\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

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

Case #1: 1 2 4
Case #2: 1 1 1
Case #3: 0 0 1 3
Case #4: -1 1
Case #5: -2 1 1

Nguồn

Google Code Jam 2015, Vòng 3, bài Log Set.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.