Cho dãy số nguyên a₁, a₂, …, a_n và một số nguyên dương M. Hãy xác định một dãy gồm n bit t₁, t₂, …, t_n (mỗi t_i bằng 0 hoặc 1) sao cho:

M = t₁a₁ + t₂a₂ + … + t_na_n.

Dữ liệu đảm bảo có nghiệm duy nhất.

Dữ liệu vào (CHONSO.INP):

Dòng 1: số nguyên dương n (5 ≤ n ≤ 20 (80% số điểm) n<=40 (20% số điểm)).
Các dòng 2 đến n+1: mỗi dòng chứa một số nguyên a_i (i = 1..n).
Dòng n+2: số nguyên dương M.

Dữ liệu ra (CHONSO.OUT):

Một dòng gồm đúng n ký tự 0/1 biểu diễn dãy bit tìm được theo thứ tự từ t₁ đến t_n.

Ví dụ

CHONSO.INP
7
11
8
23
2
45
7
34
38
  

CHONSO.OUT
0110010
  

Giải thích: 38 = 0×11 + 1×8 + 1×23 + 0×2 + 0×45 + 1×7 + 0×34 = 8 + 23 + 7.

CHONSO.INP
3
3
5
2
7
  

CHONSO.OUT
011
  

Gợi ý: 80% số điểm sử dụng thuật toán quay lùi, hãy làm bài tập về thuật toán quay lùi trước khi làm bài này

http://47.128.182.183/problem/ql2