CSES - Giant Pizza | Pizza khổng lồ

Xem PDF

Điểm: 2000 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Gia đình của Uolevi sẽ đặt một chiếc bánh pizza lớn và ăn cùng nhau. Tổng cộng có \(n\) thành viên gia đình sẽ tham gia đơn đặt hàng, và có \(m\) loại topping có thể. Bánh pizza có thể có bất kỳ số lượng topping nào.

Mỗi thành viên trong gia đình đưa ra hai mong muốn liên quan đến topping của bánh pizza. Các mong muốn có dạng "topping \(x\) là tốt/tệ". Nhiệm vụ của bạn là chọn các topping để ít nhất một mong muốn từ mọi người trở thành hiện thực (một topping tốt được thêm trong pizza hoặc một topping tệ không được thêm).

Input

  • Dòng đầu vào đầu tiên có hai số nguyên \(n\)\(m\): số lượng thành viên gia đình và loại topping. Các lớp phủ được đánh số \(1,2,\ldots,m\).
  • \(n\) dòng tiếp theo mô tả các mong muốn. Mỗi dòng có hai mong muốn với dạng + x (topping \(x\) là tốt) hoặc - x (topping \(x\) là tệ).

Output

  • In một dòng với \(m\) ký hiệu: + nếu nó được thêm và - nếu nó không được thêm cho mỗi loại topping. Bạn có thể in bất kỳ giải pháp hợp lệ nào.
  • Nếu không có giải pháp hợp lệ nào, in IMPOSSIBLE.

Constraints

  • \(1 \leq n, m \leq 10 ^ 5\)
  • \(1 \leq x \leq m\)

Example

Test 1

Input
3 5

+ 1 + 2
- 1 + 3
+ 4 - 2
Output

- + + + -

Bình luận

Không có bình luận nào.