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~, ổ đĩa 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, ..., s_n~ (~s_i \le 10^9~);
• Dòng thứ ~k~ (~1 \le k \le m~) trong ~m~ dòng sau, mỗi dòng 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 thứ ~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, ..., t_m~.

Sample Input

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

Sample Output

5
111022
4 5

Giải thích

• Với bạn thứ 1, tối đa các bức ảnh có thể sao chép được là ~5~ (ví dụ, đĩa 1 chứa bức ảnh 1, 2, 3; đĩa 2 chứa bức ảnh 5, 6). Kết quả đưa ra bằng ~4~ hoặc ~5~ đều được chấp nhận.
• Với bạn thứ 2, tối đa các bức ảnh có thể sao chép được là ~4~ (ví dụ, đĩa 1 chứa bức ảnh 1, 4; đĩa 2 chứa bức ảnh 3, 5). Kết quả đưa ra bằng ~3~ hoặc ~4~ đều được chấp nhận.
• Với bạn thứ 3, tối đa các bức ảnh có thể sao chép được là ~6~ (ví dụ, đĩa 1 chứa bức ảnh 1, 4; đĩa 2 chứa bức ảnh 2, 3, 5, 6). Kết quả đưa ra bằng ~5~ hoặc ~6~ đều được chấp nhận.

Subtasks