Giải bài trực tuyến

"You're half a world away" - 3/11/2011 Miss you

Hai năm trước, cô bé Tôm tinh nghịch được bạn mình tặng cho một món đồ chơi nhân ngày sinh nhật.

Món đồ chơi là một nhóm rất nhiều bóng đèn. Các bóng đèn được nối với nhau bằng những sợi dây điện. Mỗi bóng đèn có một công tắc. Khi bấm vào công tắc, trạng thái bật tắt của bóng đèn sẽ thay đổi.

Hai năm trôi qua, người bạn tặng món quà đó cho Tôm đã đi du học. Nhưng những gì ẩn chứa trong món đồ chơi đó dường như vẫn là một bí mật quá lớn. Tôm đã mất nhiều công sức để tìm tòi, đặt ra những thử thách cho riêng mình để có thể khám phá trọn vẹn được món đồ chơi.

Người bạn của Tôm có rất nhiều điều muốn chia sẻ. Vậy nhưng người ấy luôn ngại ngùng, e thẹn, nên đành dấu những lời thầm kín vào trong một bức thư. Để đọc hiểu được bức thư ấy, Tôm cần phải thao tác trên món đồ chơi bằng những lệnh mà bức thư chỉ ra.

Bức thư có rất nhiều lệnh. Mỗi lệnh thuộc một trong hai loại:

• Loại thứ nhất có dạng "switch i": Tôm sẽ phải bấm vào công tắc i. Khi bấm vào công tắc i, trạng thái bật tắt của bóng đèn i sẽ thay đổi.
• Loại thứ hai có dạng "print s1 s2", trong đó s1, s2 nhận một trong hai giá trị 0 hoặc 1, 0 tượng trưng cho 'tắt', 1 tượng trưng cho 'bật': Tôm cần đếm xem có bao nhiêu sợi dây điện đang nối hai bóng đèn u, v mà trạng thái bật tắt hiện tại của u là s1, trạng thái bật tắt hiện tại của v là s2.

Đầu bức thư, người bạn của Tôm viết cho Tôm trạng thái bật tắt ban đầu của các bóng đèn. Để hiểu được người bạn ấy muốn nhắn nhủ điều gì, Tôm chỉ phải thực hiện lần lượt các lệnh ở trong bức thư.

Tuy nhiên, do người bạn của Tôm quên mất rằng Tôm không phải lập trình viên, nên đã gửi một bức thư với rất nhiều lệnh. Tôm cần các thí sinh VM giúp đỡ. Các bạn hãy giúp cô bé đáng yêu này nhé!

Input

• Dòng đầu tiên là số n, m, là số lượng bóng đèn và số lượng dây điện. Các bóng đèn được đánh số từ 1 đến n. m có giá trị không vượt quá n(n-1)/2.
• m dòng sau, mỗi dòng gồm hai số nguyên x_i và y_i, thể hiện dây điện thứ i nối hai bóng đèn x_i và y_i. Không có 2 sợi dây nào nối cùng 2 bóng đèn. Không có sợi dây nào nối một bóng đèn với chính nó.
• Dòng tiếp theo chứa n số nguyên 0 hoặc 1. Số nguyên thứ i thể hiện trạng thái bật tắt ban đầu của bóng đèn thứ i. 0 thể hiện bóng đèn i đang tắt, 1 thể hiện bóng đèn i đang bật.
• Dòng tiếp theo là số q, là số lượng lệnh trong bức thư.
• q dòng tiếp theo, mỗi dòng miệu tả một dòng của bức thư. Có hai dạng lệnh:
  • "switch i" (1 ≤ i ≤ n): Thay đổi trạng thái bật tắt của bóng đèn i.
  • "print s1 s2" (s1, s2 nhận giá trị 0 hoặc 1): Cần in ra số lượng dây điện đang nối các bóng đèn có trạng thái bật tắt là s1 s2.

Output

• Với mỗi lệnh dạng print, cần in ra trên một dòng kết quả của lệnh đó.

Chấm điểm

• Bài của bạn sẽ được chấm trên thang điểm 100. Điểm mà bạn nhận được sẽ tương ứng với % test mà bạn giải đúng.
• Trong quá trình thi, bài của bạn sẽ chỉ được chấm với 1 test ví dụ có trong đề bài.
• Khi vòng thi kết thúc, bài của bạn sẽ được chấm với bộ test đầy đủ.

Giới hạn

• 1 ≤ n, m, q ≤ 100,000;
• Có 20% số test có n ≤ 100, q ≤ 10,000.

Example

Input:

5 7
1 5
1 3
2 4
2 5
3 4
3 5
4 5
0 0 0 0 0
8
print 0 0
switch 1
print 0 1
switch 5
switch 3
print 1 1
print 1 0
print 0 0

Output:

7
2
3
3
1