Cho hai số \(A\) và \(B\) khác nhau (\(1 \le A, B < 10, A \neq B\)), hãy tìm số \(S\) có đúng \(N\) chữ số, mỗi chữ số là \(A\) hoặc \(B\), sao cho phần dư khi chia \(S\) cho \(2^N\) là \(K\).

Ví dụ với \(A = 7, B = 2, N = 3\) và \(K = 5\) thì \(S = 277\) là một đáp án.

Input

• Dòng đầu ghi 2 chữ số \(A, B\) (\(1 \le A, B < 10, A \neq B\)).
• Dòng thứ 2 ghi 2 số \(N\) (\(1 \le N \le 63\)) và \(K\) (\(0 \le K < 2^N\)).

Output

• In ra số \(S\) bất kỳ nếu tồn tại. In ra -1 nếu không tồn tại số \(S\).

Example

7 2
3 5

277

Scoring

• 20% số test có \(N \le 20\).
• 30% số test có \(N \le 40\).
• 50% số test còn lại không có giới hạn gì thêm.

Notes

• Nguồn: Bắc Ninh PREVNOI 2018-2019