Halloween (viết rút gọn từ từ "All Hallows' Eve" - Đêm trước Lễ các Thánh) là một lễ hội truyền thống được tổ chức vào ngày 31 tháng 10 hàng năm, tuy nhiên, Gấu lại chưa kịp tìm gấu, do đó Gấu phải cô đơn một mình ở nhà và tự trang trí cây Halloween của bản thân. Nhưng Gấu rất thích cô gái nọ và muốn cô ta làm Gấu của mình, tuy nhiên gấu tương lai của Gấu là một người có tính cách rất "gấu", cô ta sẽ không chịu làm gấu của Gấu nếu Gấu không thỏa mãn tính cách cực "gấu" của cô ta. Bạn hãy giúp Gấu tìm gấu cho mình.

Gấu cho bạn một cây ~N~ đỉnh và ~Q~ truy vấn. Tuy nhiên cây này lại rất đặc biệt, cụ thể Gấu có thể ghi chữ T và A lên cây này. Ban đầu tất cả các đỉnh đều là chữ A, tuy nhiên, đỉnh ~1~ lại có chữ T và không thay đổi. ~Q~ truy vấn sẽ xảy ra như sau:

• S u: Thay đổi kí tự ở đỉnh ~u~ (từ T thành A và ngược lại).
• F u: Tìm chỉ số của cạnh nhỏ nhất đường đi đơn từ đỉnh ~u~ đến một đỉnh ~v \neq u~ bất kỳ mang kí tự T.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên ~\theta~ mô tả thứ tự subtask chứa test này ~(1 \leq \theta \leq 5)~.
• Dòng tiếp theo chứa hai số nguyên dương ~N, Q~ ~(2 \leq N, Q \leq 10^6)~.
• ~N-1~ dòng sau, mỗi dòng chứa hai số nguyên dương ~u, v~ mô tả một cạnh của cây ~(1 \leq u, v \leq N)~.
• ~Q~ dòng sau, mỗi dòng gồm một kí tự ~c~ và một số nguyên ~u~ được nhập dưới dạng giá trị ~u'~ mô tả truy vấn ~(c \in \{~ S, F ~\}, 0 \leq u' \leq 10^9)~.
  • Để tính ~u~ từ ~u'~, gọi ~l~ là đáp án của truy vấn loại F gần nhất (ban đầu ~l = 0~), ~u = (u' + l) \bmod (N - 1) + 2~.

Dữ liệu ra

Với mỗi truy vấn loại F, hãy in ra chỉ số của cạnh nhỏ nhất. Các cạnh được đánh số từ $1$.

Tính điểm

• Subtask ~1~ (~20~ điểm): ~1 \leq N, Q \leq 1000~.
• Subtask ~2~ (~20~ điểm): Các cạnh của cây có dạng ~(i, i+1)~ ~(1 \leq i < N)~.
• Subtask ~3~ (~20~ điểm): Các cạnh của cây có dạng ~(\lfloor\dfrac{i}{2}\rfloor, i)~ ~(2 \leq i \leq N)~ và ~1 \leq N \leq 10^5~.
• Subtask ~4~ (~20~ điểm): ~1 \leq N \leq 10^5~.
• Subtask ~5~ (~20~ điểm): Không có ràng buộc gì thêm.

Ví dụ

Đầu vào

1
7 7
2 4
3 5
2 6
3 7
1 2
2 5
F 3
S 2
F 3
S 3
S 2
F 2
F 1000000000

Đầu ra

5
1
2
2

Giải thích

• Với truy vấn đầu tiên ~u = (3 + 0) \bmod 6 + 2 = 5~, chỉ số cạnh nhỏ nhất là ~5~, đó là cạnh ~1 - 2~ trên đường đi từ đỉnh ~5~ đến đỉnh ~1~.
• Với truy vấn thứ hai ~u = (2 + 5) \bmod 6 + 2 = 3~, đỉnh ~3~ mang ký tự T.
• Với truy vấn thứ ba ~u = (3 + 5) \bmod 6 + 2 = 4~, chỉ số cạnh nhỏ nhất là ~1~, đó là cạnh ~2 - 4~ trên đường đi từ đỉnh ~4~ đến đỉnh ~3~.
• Với truy vấn thứ tư ~u = (3 + 1) \bmod 6 + 2 = 6~, đỉnh ~6~ mang ký tự T.
• Với truy vấn thứ năm ~u = (2 + 1) \bmod 6 + 2 = 5~, đỉnh ~5~ mang ký tự T.
• Với truy vấn thứ sáu ~u = (2 + 1) \bmod 6 + 2 = 5~, chỉ số cạnh nhỏ nhất là ~2~, đó là cạnh ~3 - 5~ trên đường đi từ đỉnh ~5~ đến đỉnh ~3~.
• Với truy vấn cuối cùng ~u = (10^9 + 2) \bmod 6 + 2 = 2~, chỉ số cạnh nhỏ nhất là ~2~, đó là cạnh ~3 - 5~ trên đường đi từ đỉnh ~2~ đến đỉnh ~3~.