Bài tập

Một đoàn xe chở hàng đang di chuyển qua một tuyến đường dài. Trên tuyến đường này có \(n\) trạm kiểm soát, được đánh số liên tục từ \(1\) đến \(n\) từ trái sang phải, trạm kiểm soát thứ \(i\) đang giữ một kiện hàng có trọng lượng \(a_{i}\) kg.

Để không bị CSGT phạt vì quá giới hạn trọng tải của xe, bạn không thể vận chuyển nhiều hơn \(s\) đơn vị hàng hóa trong một chuyến xe. Bạn cần chia số hàng hóa thành nhiều chuyến sao cho:

• Mỗi chuyến xe không chở quá \(s\) đơn vị hàng, và mỗi chuyến xe sẽ vận chuyển các kiện hàng nằm trên một đoạn liên tiếp các trạm kiểm soát.

• Chi phí vận chuyển của một chuyến xe phụ thuộc vào kiện hàng nặng nhất trong chuyến đó và số lượng kiện hàng có trong chuyến. Cụ thể hơn, chi phí vận chuyển một chuyến chính là tổng của trọng lượng kiện hàng lớn nhất và số lượng kiện hàng trong chuyến trừ \(1\).

• Tổng chi phí vận chuyển của toàn bộ đoàn xe phải được tối ưu sao cho nhỏ nhất.

Input

• Dòng đầu tiên chứa hai số nguyên \(n, s\) \((1 \leq n \leq 2 \times 10^6, 1 \leq s \leq 10^{18})\) --- số lượng trạm kiểm soát và tải trọng tối đa của mỗi chuyến đi.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, ..., a_n\) \((1 \leq a_i \leq \min(s, 10^9))\) --- trọng lượng của kiện hàng cần vận chuyển tại mỗi trạm.

Output

In ra một số nguyên duy nhất --- tổng chi phí vận chuyển tối thiểu để hoàn thành nhiệm vụ.

Example

6 7
3 1 5 2 1 4

15

Scoring

• \(20\%\) số test tương ứng với \(20\%\) số điểm có \(n \leq 20\)
• \(20\%\) số test tương ứng với \(20\%\) số điểm có \(n \leq 100\)
• \(20\%\) số test tương ứng với \(20\%\) số điểm có \(n \leq 5000\).
• \(20\%\) số test tương ứng với \(20\%\) số điểm có \(n \leq 2 \times 10^5\).
• \(20\%\) số test tương ứng với \(20\%\) số điểm có \(n \leq 2 \times 10^6\).

Cho một cây có \(n\) đỉnh (được đánh số từ \(1\) đến \(n\)) và có gốc tại đỉnh \(1\). Mỗi đỉnh đều có hai giá trị gắn liền với nó: \(a_i\) và \(b_i\) cho đỉnh thứ \(i\).

Bạn có thể nhảy từ một đỉnh đến bất kỳ đỉnh nào trong cây con của nó. Chi phí cho một lần nhảy từ đỉnh \(x\) đến đỉnh \(y\) là tích của \(a_x\) và \(b_y\). Tổng chi phí của một đường đi được tạo thành từ một hoặc nhiều lần nhảy là tổng chi phí của các lần nhảy riêng lẻ.

Với mỗi đỉnh, hãy tính toán tổng chi phí tối thiểu để đi đến một đỉnh lá bất kỳ từ đỉnh đó. Lưu ý rằng đỉnh gốc (đỉnh 1) không bao giờ được coi là đỉnh lá, ngay cả khi nó chỉ có một bậc (degree).

Bạn không thể nhảy từ một đỉnh đến chính nó.

Input

• Dòng đầu tiên chứa một số nguyên \(n\) (\(2 \le n \le 10^5\)) --- số lượng đỉnh trong cây.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(-10^5 \le a_i \le 10^5\)).
• Dòng thứ ba chứa \(n\) số nguyên \(b_1, b_2, \dots, b_n\) (\(-10^5 \le b_i \le 10^5\)).
• \(n-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u_i\) và \(v_i\) (\(1 \le u_i, v_i \le n\)) mô tả một cạnh nối giữa hai đỉnh \(u_i\) và \(v_i\).

Output

In ra \(n\) số nguyên cách nhau bởi dấu cách. Số thứ \(i\) trong đó là chi phí tối thiểu để đi từ đỉnh \(i\) đến bất kỳ đỉnh lá nào.

Example

3
2 10 -1
7 -7 5
2 3
2 1

10 50 0 

4
5 -10 5 7
-8 -80 -3 -10
2 1
2 4
1 3

-300 100 0 0 

Scoring

• Có \(30\%\) số test tương ứng với \(30\%\) số điểm có \(N \leq 100\).
• Có \(30\%\) số test tương ứng với \(30\%\) số điểm có bậc của các đỉnh trong cây không vượt quá \(2\).
• Có \(40\%\) số test tương ứng với \(40\%\) số điểm còn lại không có ràng buộc gì thêm.

Cho dãy số nguyên không âm \(a_1, a_2, \ldots, a_n\). Xét tất cả \(n \times (n - 1)\ /\ 2\) cặp \((i, j)\) mà \(1 \le i < j \le n\) để tạo dãy gồm \(n \times (n - 1)\ /\ 2\) phần tử tương ứng với cặp \((i, j)\) có giá trị \(a_i + a_j\).

Yêu cầu: Tính xor của tất cả các phần tử trong dãy mới tạo.

Input

• Dòng đầu chứa số nguyên \(n\ (n \le 3.10^5)\).
• Dòng thứ hai gồm \(n\) số nguyên không âm có giá trị không vượt quá \(10^9\) mô tả dãy \(a_1, a_2, \ldots, a_n\).

Output

• Gồm một dòng là giá trị tính được.

Example

3
1 2 3

2

Bạn được cho một dãy số nguyên, ban đầu dãy này rỗng. Lần lượt thực hiện \(Q\) truy vấn thuộc một trong ba dạng:

• add \(x\): Thêm một phần tử với giá trị \(x\) vào dãy (Có thể tồn tại nhiều phần tử cùng giá trị

• del \(x\): Xóa bỏ khỏi dãy một phần tử với giá trị \(x\)

• cnt \(x\): Đếm xem trong dãy tồn tại bao nhiêu số \(y\) mà \(x\) & \(y\) = \(y\), trong đó & là phép AND bit

Yêu cầu: Với mỗi truy vấn loại cnt, bạn hãy in ra kết quả tương ứng

Input

Dòng đầu tiên chứa số nguyên dương \(Q\) \((Q \leq 2 \times 10^5)\) là số truy vấn.

\(Q\)dòng tiếp, mỗi dòng mô tả một truy vấn, \(x \leq 2^{16}\) trong mọi truy vấn.

Output

In ra nhiều dòng, mỗi dòng là kết quả cho truy vấn loại cnt tương ứng trong bộ dữ liệu

Example

7
add 11
cnt 15
add 4
add 0
cnt 6
del 4
cnt 15

1
2
2

Scoring

Đảm bảo với mọi test, khi thực hiện thao tác del \(x\), \(x\) đã xuất hiện trong dãy.

\(30\%\) số test có \(Q \leq 1000\).

\(30\%\) số test có \(x \leq 2^8\).

\(40\%\) số test còn lại không có ràng buộc gì thêm.