Bạn bè

Quân vừa tham gia ICPC WF cùng \(n\) người bạn được đánh số từ \(1\) đến \(n\). Tại đây đã có \(m\) tình bạn nảy nở, tình bạn thứ \(i\) là giữa \(u_{i}\) và \(v_{i}\), các tình bạn được đánh số theo thứ tự thời gian. Hiện tại Quân chưa kết bạn với ai và anh muốn kết bạn theo cách sau:

Bước \(1\) : Nếu đã kết bạn với tất cả thì dừng.

Bước \(2\): Chọn \(x\) nhỏ nhất mà chưa kết bạn. Mở rộng quan hệ với \(x\) theo cách sau:

• Kết bạn với \(x\).

• \(x\) sẽ giới thiệu cho Quân các bạn bè của \(x\) theo thứ tự thời gian;

• Quân sẽ mở rộng quan hệ với từng người một vừa được \(x\) giới thiệu, theo thứ tự. Nói cách khác, quá trình mở rộng quan hệ là một quá trình đệ quy (tìm kiếm theo chiều sâu).

Bước \(3\) : Quay lại bước \(1\).

Kết thúc quá trình, Quân đã kết bạn với tất cả mọi người. Quân sẽ tổ chức \(Q\) trò chơi, mỗi trò chơi sẽ mời những người từ \(l\) tới \(r\) tham gia. Khi \(x\) tham gia trò chơi, anh ta sẽ để ý các bạn bè của mình trong trò chơi. Nếu \(y\) là bạn của \(x\) và có tham gia trò chơi, \(x\) nghĩ rằng Quân thiên vị nếu \(y\) trở thành bạn của Đắc trước \(x\) . Nếu không có \(y\) nào như vậy, \(x\) sẽ nghĩ trò chơi này công bằng. Mức độ công bằng của trò chơi là số người nghĩ trò chơi này công bằng. Hãy giúp Quân tính toán mức độ công bằng của từng trò chơi.

 -

Input

Dòng đầu chứa \(n\) \(m\) \(Q\) \(s\) (trong đó \(s\) dùng để xử lí dữ liệu online).

\(m\) dòng tiếp theo, dòng thứ \(i\) chứa \(u_{i}\) và \(v_{i}\).

\(Q\) dòng tiếp theo, mỗi dòng chứa hai số \(x\) \(y\), khi đó \(l\) và \(r\) được tính như sau:

• Gọi \(last\) là kết quả cho truy vấn ngay trước truy vấn này, hoặc \(last = 0\) nếu đây là truy vấn đầu tiên

• \(l = (x + s \cdot last - 1) \% n + 1\).

• \(r = (x + s \cdot last - 1) \% n + 1\).

• Nếu \(l > r\) thì đổi giá trị \(l\) và \(r\).

Output

Ghi \(Q\) dòng là kết quả cho \(Q\) trò chơi.

Example

4 3 5 0
1 2
1 3
2 4
3 4
1 3
1 4
3 2
3 2

2
1
1
2
2

Scoring

Trong tất cả các test: \(1 \leq n, m, Q, x, y \leq 10^5; 0 \leq s \leq 1\)

Có \(20\%\) số test có \(s = 0\) và mỗi người chỉ có nhiều nhất một người bạn (ngoài Quân).

Có \(20\%\) số test với mỗi người chỉ có nhiều nhất một bạn bè.

Có \(20\%\) số test với \(s = 0\).

Có \(40\%\) số test với ràng buộc gốc.