Trong một hội nghị cấp cao của CLB H3.2, có tất cả ~n~ SV và mỗi người sẽ biết một vài ngôn ngữ lập trình. Thư ký Luna ghi nhận được có tất cả ~m~ cặp trong số họ có biết chung ngôn ngữ lập trình và có thể "chém gió trực tiếp" được với nhau. Độ danh tiếng của một người ~X~ là số lượng người mà ~X~ có thể chém gió trực tiếp được. Tất nhiên sẽ có những người ~A, B~ cũng muốn "chém gió gián tiếp" nếu như thỏa mãn điều kiện: có thể xếp họ ngồi vào một dãy ghế mà ~A~ đầu dãy này, ~B~ đầu dãy kia và ở giữa là vài người khác sao cho hai người ngồi cạnh nhau trên ghế thì có thể "chém gió trực tiếp" được.

Hãy đếm số cặp ~(A,B)~ là những người có cùng độ danh tiếng và ~A,B~ có thể chém gió trực tiếp hoặc gián tiếp với nhau.

Input

Dòng đầu tiên gồm số nguyên dương ~n, m~ với ~2 \le n \le 10^5~ và ~0 \le m \le 3.10^5.~

Dòng tiếp theo gồm các cặp số ~(a,b)~ với ~1 \le a \neq b \le n~ cho biết số thứ tự của những người có thể chém gió trực tiếp được. Do thư ký Luna cũng hơi lẩm cẩm nên một cặp có thể bị xuất hiện nhiều lần.

Output

Đáp số của bài toán.

Sample input 1

3 2
1 2
2 3

Sample output 1

1

Sample input 2

5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

Sample output 2

10

Giải thích: trong VD1 đã cho, hai người thứ 1 và 3 có thể chém gió gián tiếp thông qua 2 và họ cùng độ danh tiếng là 1 nên ~(1,3)~ thỏa mãn điều kiện.

Subtasks:

• Có 50% số test ứng với ~n \le 10^4.~
• Có 50% số test không có ràng buộc nào thêm.

Anh Long là một đại ca máu lạnh khét tiếng của IUH, anh sống trong một tòa lâu đài rộng lớn với thú cưng là các con vịt. Anh Long nuôi bầy vịt trong một căn phòng hình chữ nhật khép kín và ngăn vách cho chúng tạo thành các phòng nhỏ. Mỗi đêm, để vịt có sự riêng tư, anh cho mỗi con ngủ trong một phòng. Hệ thống vách tường của căn phòng của vịt được mô tả như sau: góc dưới-trái là (0,0) và góc trên-phải là ~(A,B)~ và

• Có ~m~ bức tường ngang được mô tả bởi đoạn thẳng nối điểm ~(0,b_i)~ với ~(A,b_i)~ ở đây ~0<b_i<B~ với mọi ~i=1,2,…,m~. </li>
• Có ~n~ bức tường dọc được mô tả như là các đoạn thẳng nối điểm ~(a_i,0)~ với ~(a_i,B)~ ở đây ~0<a_i<A~ với mọi ~i=1,2,…,n~. </li>
• Chu vi của hình chữ nhật cũng là các bức tường, như vậy căn phòng sẽ được chia thành ~(m+1)×(n+1)~ phòng nhỏ.

Đến ban ngày, để lũ vịt đỡ cô đơn, anh sẽ dùng hệ thống tự động mở một số đoạn tường ngang hoặc dọc của một số phòng sao cho tất cả các phòng đều đi đến được nhau. Hãy tính tổng độ dài bé nhất của các đoạn tường mà anh Long tháo để có thể làm được điều trên?

Input

• Dòng đầu tiên chứa 4 số nguyên dương ~A,B,n,m~ với ~1≤A,B≤10^9~ và ~n,m≤ 25000~.
• Trong ~n~ dòng tiếp theo lần lượt chứa các số nguyên ~a_1,a_2,…,a_n~ và ~m~ dòng cuối cùng lần lượt chứa các số nguyên ~b_1,b_2,…,b_m~.

Output

Một số nguyên duy nhất là tổng độ dài nhỏ nhất của các đoạn tường cần phá.

Sample input

15 15 5 2
2
5
10
6
4
11
3

Sample output

44

Subtasks:

• Subtask 1: ~n,m≤2000~
• Subtask 2: ~n,m≤25000~

Nhà cô Ban có nuôi một đàn gà đi bộ rất chắc thịt ngọt xương, một loại đặc sản đắt tiền. Đến mùa, cô Ban lại giết thịt để cung cấp các suất ăn dinh dưỡng cho lab H3.2. Đàn gà đi bộ của cô được nuôi nhốt trong chuồng có dạng hình tròn. Bên trong chuồng này có ~n~ căn phòng đánh số theo chiều kim đồng hồ lần lượt là ~1,2,…,n~. Mỗi phòng đều có hai cửa thông sang phòng bên cạnh và một cửa hướng ra bên ngoài để gà đi vào.

Cô Ban muốn bố trí ~r_i~ con gà ở phòng ~i~ với ~i=1,2,..,n~. Để đàn gà đi vào chuồng một cách có trật tự, cô chỉ mở ~k~ trong số ~n~ cánh cửa hướng ra bên ngoài đón các con gà về chuồng. Các con gà sau khi vào một trong ~k~ cửa sẽ di chuyển theo chiều kim đồng hồ đến phòng đầu tiên chưa đủ số gà cần chứa và ở lại phòng này.

Yêu cầu: hãy giúp cô Ban chọn ra ~k~ cửa hướng ra ngoài để tổng đoạn đường di chuyển của tất cả các con gà sau khi đi vào chuồng là nhỏ nhất. Khi con gà di chuyển đến phòng kế tiếp thì nó phải di chuyển 1 đơn vị độ dài.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n,k~ với ~3≤n≤100; 1≤k≤7.~
• Trong ~n~ dòng tiếp theo, dòng thứ ~i~ chứa số nguyên dương ~r_i~ với ~1≤r_i≤10^6~

Output

Một số nguyên duy nhất là kết quả tìm được.

Sample input

6 2
2
5
4
2
6
2

Sample output

14

Giải thích: cô Ban mở cửa ngoài các phòng ~2~ và ~5~. Khi đó có ~11~ con gà đi vào cửa ~2~ và tổng khoảng cách đi bộ của các con gà này là ~8~ để vào các chuồng ~2, 3, 4~. Có ~10~ con gà đi vào cửa ~5~ và tổng khoảng cách di chuyển của các con gà này là ~6~ để vào các chuồng ~5, 6~ và ~1~.

Trong các môn học thì anh Lộc thích nhất môn CP, và trong các mảng kiến thức CP, Lộc thích nhất việc dùng cây phân đoạn. Lộc đã luyện nó ngày đêm đến hàng chuyên gia. Một hôm, có anh Aquarius cũng xưng là nghệ nhân về cây phân đoạn đến thử thách anh Lộc một bài toán quen mà lạ như sau: Cho ~n~ số tự nhiên ~a_1,a_2,…,a_n~ và ~2~ loại thao tác:

• Loại 1: tính tổng các phần tử trong đoạn ~[l,r].~
• Loại 2: áp dụng phép toán XOR với ~x~ cho trước cho từng phần tử trong đoạn ~[l,r].~

Cho danh sách ~m~ thao tác thuộc 2 loại trên, anh Lộc cần thực hiện tất cả các thao tác đã cho và đối với mỗi thao tác tính tổng, in ra kết quả nhận được. Anh Lộc đã giải xong subtask 1 dùng vét cạn rồi, còn subtask 2 thì anh... đang suy nghĩ thêm ^^. Bạn hay thử sức nhé, vì nghệ nhân Aquarius hình như cũng đang quên solution rồi T_T.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ và dòng tiếp theo là các số tự nhiên ~a_1,a_2,…,a_n~.
• Dòng thứ 3 chứa số nguyên dương ~m~ là số thao tác và trong ~m~ dòng tiếp theo mô tả ~m~ thao tác theo định dạng:
• ~1~ ~l~ ~r~: Tính tổng phần tử trong đoạn ~[l,r];~
• ~2~ ~l~ ~r~ ~x~: Áp dụng phép toán XOR với ~x~ cho tất cả phần tử trong đoạn ~[l,r].~

Output trả lời tất cả các câu hỏi ở thao tác loại 1.

Sample input

5
4 10 3 13 7
8
1 2 4
2 1 3 3 
1 2 4 
1 3 3 
2 2 5 5
1 1 5
2 1 2 10
1 2 3

Sample output

26
22
0
34
11

Subtasks

• Có 60% test ứng với ~n,m≤2.10^3~ còn ~x, a_i <= 10^6~.
• Có 40% test ứng với ~n≤2.10^5,m≤2.10^5~ còn ~x, a_i≤10^6~.