Trong buổi họp lớp, Alice đã chụp được \(n\) bức ảnh, các bức ảnh được đánh số từ \(1\) đến \(n\). Bức ảnh thứ \(i\) (\(1 \le i \le n\)) có kích thước \(s_i\).

Có \(m\) bạn trong lớp muốn nhờ Alice sao chép các bức ảnh. Bạn thứ \(k\) (\(1 \le k \le m\)) sẽ đưa cho Alice hai ổ đĩa, ổ đĩa thứ nhất có sức chứa \(a_k\), ổ thứ hai có sức chứa \(b_k\) và một danh sách \(L_k\) là các bức ảnh không cần sao chép. Bạn thứ \(k\) mong muốn có thể sao chép được nhiều bức ảnh nhất vào hai ổ đĩa gồm các bức ảnh không thuộc danh sách \(L_k\).

Alice không chắc chắn có thể sao chép được tối đa các bức ảnh theo cách tối ưu. Tuy nhiên, bạn thứ \(k\) vẫn vui vẻ nếu số lượng bức ảnh sao chép được không ít hơn \((g_k - 1)\), trong đó \(g_k\) là số lượng tối đa các bức ảnh có thể sao chép được theo cách tối ưu.

Yêu cầu: Hãy giúp Alice đưa ra kế hoạch sao chép các bức ảnh cho các bạn. Giả sử \(t_k\) là số lượng bức ảnh mà Alice có thể sao chép cho bạn thứ \(k\) (\(1 \le k \le m\)), giá trị này được chấp nhận nếu \((g_k - 1) \le t_k \le g_k\).

Input

• Dòng đầu chứa hai số nguyên dương \(n, m\) (\(n, m \le 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên dương \(s_1, s_2, \ldots, s_n\) (\(s_i \le 10^9\)).
• Dòng thứ \(k\) (\(1 \le k \le m\)) trong \(m\) dòng sau có dạng:
  • Hai số đầu tiên là \(a_k, b_k\) (\(a_k, b_k \le 10^9\)).
  • Số thứ ba là số \(|L_k|\), là số bức ảnh mà bạn \(k\) không thích.
  • Tiếp theo là \(|L_k|\) số, là chỉ số các bức ảnh thuộc danh sách \(L_k\).

Tổng số lượng phần tử trong \(m\) danh sách không vượt quá \(10^5\) (\(\sum_{k=1}^{m}|L_k| \le 10^5\)).

Output

• Dòng đầu chứa số nguyên \(t_1\) là số bức ảnh có thể sao chép cho bạn thứ nhất.
• Dòng thứ hai là một xâu độ dài \(n\) chỉ gồm các kí tự 0, 1, 2 mô tả cách sao chép các bức ảnh cho bạn thứ nhất, trong đó kí tự thứ \(i\) (\(1 \le i \le n\)) bằng 0 cho biết bức ảnh thứ \(i\) không được sao chép, bằng 1 hoặc 2 cho biết bức ảnh \(i\) được sao chép vào đĩa 1 hoặc đĩa 2.
• Do dữ liệu ghi ra quá lớn nên với các bạn còn lại chỉ cần đưa ra số lượng bức ảnh có thể sao chép được. Cụ thể, dòng thứ ba chứa \(m - 1\) số \(t_2, t_3, \ldots, t_m\).

Example

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

5
111022
4 5

Scoring

• Subtask 1 (\(25\%\) số điểm): \(n \le 10\); \(m \le 3\); \(a_k, b_k \le 1000\); \(|L_k| = 0\).
• Subtask 2 (\(25\%\) số điểm): \(n \le 50\); \(m \le 3\); \(a_k, b_k \le 1000\).
• Subtask 3 (\(25\%\) số điểm): \(|L_k| = 0\).
• Subtask 4 (\(25\%\) số điểm): Không có ràng buộc nào thêm.