Xếp ba lô

Trong chuyến công tác nhiều ngày, giáo sư J đã thu thập được $n$ mẫu vật. Mẫu vật thứ $i$ ($i=1,2,\dots ,n$) có khối lượng $m_i$ gam và được giáo sư đánh giá có mức độ quan trọng là $v_i$. Giáo sư đã chuẩn bị một túi xách tay có thể chứa không quá $W_1$ gam và một va li có thể chứa không quá $W_2$ gam. Vấn đề mà giáo sư gặp phải là lựa chọn những mẫu vật và xếp chúng vào túi hay va li thỏa mãn các yêu cầu sau:

1. Tổng khối lượng các mẫu vật đựng trong túi xách không vượt quá $W_1$;
2. Tổng khối lượng các mẫu vật đựng trong va li không vượt quá $W_2$;
3. Tổng mức độ quan trọng của các mẫu vật được chọn là lớn nhất.

Yêu cầu: Cho $W_1,W_2$ và thông tin về $n$ mẫu vật, hãy đưa ra cách lựa chọn và xếp các mẫu vật thỏa mãn yêu cầu của giáo sư. Nếu có nhiều cách xếp đạt tổng mức độ quan trọng lớn nhất, in ra một cách bất kỳ.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên dương $n,W_1,W_2$ ($W_1\le 5000$; $W_1<W_2\le 50000$);
• Dòng thứ $i$ trong $n$ dòng tiếp theo mô tả mẫu vật thứ $i$ gồm hai số nguyên dương $m_i,v_i$ ($m_i\le W_2$; $v_i\le 5$).

Dữ liệu ra

In ra một dòng chứa $n$ số mô tả cách lựa chọn và xếp các mẫu vật. Cụ thể, số thứ $i$ bằng $0$ nếu mẫu vật thứ $i$ không được chọn, bằng $1$ nếu được chọn và xếp vào túi xách, bằng $2$ nếu được chọn và xếp vào va li.

Ràng buộc

• $1\le n\le 1000$; nếu $n>50$ thì mọi mẫu vật có mức độ quan trọng như nhau;
• $1\le W_1\le 5000$, $W_1<W_2\le 50000$;
• $1\le m_i\le W_2$, $1\le v_i\le 5$.

Subtasks

• Có $40\%$ số test ứng với $40\%$ số điểm của bài có $n\le 10$;
• Có $30\%$ số test khác ứng với $30\%$ số điểm của bài có $n\le 50$ và các mẫu vật có khối lượng là bội của $100$;
• Có $15\%$ số test khác ứng với $15\%$ số điểm của bài có $n\le 50$;
• Có $15\%$ số test khác ứng với $15\%$ số điểm của bài có $n\le 1000$ và các mẫu vật có mức độ quan trọng như nhau.

Ví dụ