Nhắm mắt (Eyes Closed)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Mảng số nguyên. Thao tác loại 1 chọn ngẫu nhiên đều một phần tử ở mỗi trong hai đoạn không giao nhau rồi hoán đổi chúng. Loại 2 hỏi kỳ vọng tổng trên một đoạn sau các thao tác trước.

Input

Dòng đầu chứa $n,q$. Dòng thứ hai chứa $n$ số nguyên của mảng ban đầu. Mỗi trong $q$ dòng sau là:

• 1 l1 r1 l2 r2: hai đoạn $[l_1,r_1]$ và $[l_2,r_2]$ không giao nhau; chọn ngẫu nhiên đều một vị trí trong mỗi đoạn rồi hoán đổi hai giá trị.
• 2 l r: hỏi kỳ vọng tổng trên đoạn $[l,r]$.

Output

Mỗi truy vấn loại 2 in một số thực; sai số tuyệt đối hoặc tương đối không quá $10^{-4}$.

Subtask

• Subtask 1 (20%): $n$ và số thao tác không vượt 30; các điều kiện còn lại giữ như đề đầy đủ.

• Subtask 2 (30%): $n$ và số thao tác không vượt 3000; các điều kiện còn lại giữ như đề đầy đủ.

• Subtask 3 (50%): toàn bộ giới hạn:

• $2\le n\le10^5$

• $1\le q\le10^5$

• $1\le a_i\le10^9$

• Hai đoạn của thao tác loại 1 không giao nhau.

Ví dụ

Input

4 4
1 1 2 2
1 2 2 3 3
2 1 2
1 1 2 3 4
2 1 2

Output

3.0000000000
3.0000000000

Giải thích

Sau phép hoán đổi ngẫu nhiên đầu tiên, kỳ vọng tổng đoạn [1,2] vẫn bằng 3. Phép hoán đổi tiếp theo cũng giữ kỳ vọng truy vấn cuối bằng 3.