Có \(n\) \((n \ge 2)\) đồng tiền xu trong đó có đúng một đồng tiền giả. Đồng tiền giả này có khối lượng nhẹ hơn so với các đồng tiền thật (tất cả các đồng tiền thật có khối lượng bằng nhau). Sử dụng cân thăng bằng, cân sẽ cho ta biết bên nào nặng hơn, bên nào nhẹ hơn hoặc hai bên bằng nhau. Để tìm đồng tiền giả ta đánh số các đồng tiền từ \(1\) đến \(n\), sau đó tiến hành cân một số lần, mỗi lần cân là đặt một lượng đồng xu bằng nhau lên đĩa bên trái và đĩa bên phải. Kết quả của các lần cân được ghi lại.

Yêu cầu: Xác định đồng xu giả sử dụng các kết quả được ghi chép lại.

Input

• Dòng đầu là hai số nguyên \(n\) và \(k\) trong đó \(n\) là số đồng tiền xu, \(k\) là số lần cân được ghi chép lại.
• Tiếp theo là \(k\) dòng mô tả \(k\) lần cân, mỗi dòng mô tả một lần cân. Lần cân thứ \(i\) có dạng:
  • Bắt đầu bằng số nguyên \(s_i\) \((1 \le s_i \le \frac{n}{2})\) là số đồng xu được đặt lên mỗi đĩa cân.
  • Tiếp theo là \(s_i\) số nguyên là số hiệu các đồng xu được đặt bên trái.
  • Tiếp theo là \(s_i\) số nguyên là số hiệu các đồng xu được đặt bên phải.
  • Cuối cùng là một số mô tả kết quả lần cân đó:
    • 0: nếu cân thăng bằng.
    • 1: nếu bên trái nặng hơn.
    • 2: nếu bên phải nặng hơn.

Dữ liệu đảm bảo đúng đắn và tổng \(s_1 + s_2 + \dots + s_k\) không vượt quá \(10^5\).

Output

• Ghi ra một số nguyên là số hiệu đồng xu giả hoặc ghi ra số \(0\) nếu không thể tìm ra duy nhất một đồng xu giả từ các thông tin đã cho.

Example

2 1
1 1 2 1

2

6 2
1 1 2 0
2 1 2 3 4 0

0

Constraints

• Có \(30\%\) số test của bài có \(n \le 3\).
• Có \(40\%\) số test khác của bài có \(n \le 100\).
• Có \(30\%\) số test còn lại của bài có \(n \le 10^9\).