Các bạn có biết để sản xuất ra những cây Bīngqílín 2023 thơm ngon bổ dưỡng, thưởng thức là mê, thì Bedao đã lấy nguyên liệu từ đâu không? Tất cả các nguyên liệu để sản xuất đều là nguyên liệu từ hoa quả tự nhiên. Và để có những nguyên liệu này thì Bedao đã nhờ những chú kiến trong rừng thu lượm những nguyên liệu làm kem, và đổi lại Bedao cũng trả cho những chú kiến những cây kem Bīngqílín 2023.

Hôm nay Bedao muốn tối ưu hóa quá trình vận chuyển nguyên liệu, nên bạn ấy quyết định theo dõi xem các chú kiến thực hiện di chuyển ra sao. Khi đến thăm đường dây vận chuyển nguyên liệu, Bedao quan sát thấy rằng tất cả các chú kiến đều di chuyển nguyên liệu đúng theo một trục thẳng. Trên trục đường đi có ~n~ chú kiến. Chú kiến thứ ~i~ ban đầu đứng ở vị trí ~x_i~, có khối lượng là ~w_i~ và đang hướng về chiều âm/chiều dương của trục đường đi.

Sau một hồi quan sát di chuyển, Bedao nhận thấy:

• Tất cả các chú kiến đều di chuyển với vận tốc là ~1~ đơn vị độ dài/giây.

• Khi hai chú kiến có cùng khối lượng chạm nhau, chú kiến đang hướng về bên phải sẽ hướng về bên trái, và chú kiến còn lại sẽ hướng về bên phải.

• Khi hai chú kiến khác khối lượng chạm nhau, chú kiến nhẹ hơn sẽ bị chú kiến nặng hơn hất văng ra khỏi trục di chuyển. Tuy chú kiến nhẹ hơn không bị physical damage, nhưng chú lại rất buồn do emotional damage, và bò về tổ. Chú kiến nặng hơn tiếp tục di chuyển theo hướng đi đang di chuyển.

Bedao kết luận rằng mấu chốt cho sự hiệu quả trong quá trình di chuyển của những chú kiến chính là thời gian mà các chú kiến vận chuyển trên trục (vì nếu chú kiến nào bò về tổ thì các chú kiến đều bị emotional damage). Để quan sát được kĩ hơn, Bedao sẽ thực hiện ~q~ thí nghiệm, mỗi thí nghiệm có một trong hai dạng sau:

• 1 ~i~  – đổi hướng di chuyển ban đầu của chú kiến thứ ~i~.

• 2 ~i~  – giả sử tất cả các chú kiến bắt đầu di chuyển, Bedao muốn biết chú kiến thứ ~i~ sẽ dành bao nhiêu thời gian trên trục di chuyển.

Cho mô tả của ~n~ chú kiến và danh sách ~q~ thí nghiệm theo thứ tự thực hiện, hãy giúp Bedao trả lời tất cả các thí nghiệm loại 2.

Input

Dòng đầu tiên gồm hai số nguyên ~n~ và ~q~ (~1 \le n, q \le 200\,000~).

Dòng tiếp theo chứa ~n~ số nguyên ~x_1, x_2, \ldots, x_n~ (~-10^9 \le x_1 < x_2 < \ldots < x_n \le 10^9~)  – vị trí ban đầu của các chú kiến.

Dòng tiếp theo chứa ~n~ số nguyên ~w_1, w_2, \ldots, w_n~ (~1 \le w_i \le n~)  – khối lượng của các chú kiến.

Dòng tiếp theo chứa xâu ~s~ có độ dài ~n~ (~s_i \in \lbrace \texttt{L}, \texttt{R} \rbrace~). ~s_i = \texttt{L}~ khi ban đầu chú kiến thứ ~i~ đang hướng về chiều âm của trục di chuyển. ~s_i = \texttt{R}~ khi chú kiến thứ ~i~ ban đầu đang hướng về chiều dương của trục di chuyển.

Mỗi dòng trong ~q~ dòng tiếp chứa hai số nguyên ~type~ và ~i~ (~type \in \lbrace 1, 2 \rbrace~, ~1 \le i \le n~)  – mô tả của truy vấn theo định đạng ở trên.

Output

Với mỗi truy vấn loại 2, nếu chú kiến không bao giờ rời khỏi trục di chuyển, hãy in ra ~-1~. Ngược lại hãy in ra một số duy nhất là thời gian ở trên trục di chuyển của chú kiến đang xét.

Với mỗi truy vấn, đáp án của bạn được cho là chính xác nếu như số tuyệt đối hoặc tương đối không quá ~10^{-9}~.

Cụ thể, nếu đáp án của bạn là ~a~ và đáp án của ban tổ chức là ~b~, vậy đáp án của bạn sẽ được chấp nhận khi và chỉ khi ~\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-9}~.

Scoring

• Subtask 1 (~300~ điểm): ~n, q, |x_i| \le 100~.

• Subtask 2 (~700~ điểm): ~w_i \ne w_j~ với mọi ~i \ne j~.

• Subtask 3 (~700~ điểm): tất cả mọi truy vấn đều là truy vấn loại 2.

• Subtask 4 (~700~ điểm): không có ràng buộc gì thêm.

Tổng cộng bài toán có ~2400~ điểm.

Sample Input 1

5 11
1 2 3 4 5
1 4 3 5 2
RRLRL
2 1
2 2
2 3
2 4
2 5
1 4
2 1
2 2
2 3
2 4
2 5

Sample Output 1

-1
-1
0.500000000
-1
0.500000000
1.500000000
1.000000000
0.500000000
-1
-1

Sample Input 2

5 3
-6 -4 -2 0 2
2 2 4 3 4
RLRLL
2 1
2 2
2 4

Sample Output 2

-1
4.000000000
1.000000000