Với một số nguyên dương \(x\), ta gọi \(Next(x)\) là số nguyên dương nhỏ nhất lớn hơn \(x\) nhưng có cùng số lượng bit \(1\) với \(x\) khi biểu diễn trong dạng nhị phân.

Ví dụ: \(Next(1) = 2; Next(6) = 9\).

Kí hiệu: \(Next^k(x) = Next(Next(...(Next(x))))\) (có tổng cộng \(k\) lần thực hiện hàm trong dấu ..., ví dụ \(Next^3(x) = Next(Next(Next(x)))\)).

Yêu cầu: Cho số nguyên dương \(x\) (\(x \le 10^{15}\)) và số nguyên dương \(k\), hãy tìm \(Next^k(x)\), nếu giá trị này vượt quá \(10^{15}\) thì đưa ra giá trị \(-1\).

Input

• Dòng đầu là số \(t\).
• \(t\) dòng sau, mỗi dòng chứa hai số nguyên \(x\) và \(k\).

Output

• Gồm \(t\) dòng, mỗi dòng là kết quả tương ứng với dữ liệu vào.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(k \le 10^2; t \le 10\).
• Subtask \(2\) (\(50\%\) số điểm): \(k \le 10^{15}; t \le 1000\).

Example

2
1 2
6 1

4
9

Trên hai đồ thị vô hướng, liên thông \(G_1\) và \(G_2\) cùng có \(n\) đỉnh. Với hai đỉnh \(s\) và \(t\), đặt robot thứ nhất ở đỉnh \(s\) trên đồ thị \(G_1\), robot thứ hai cũng ở đỉnh \(s\) trên đồ thị \(G_2\), tìm cách di chuyển hai robot cùng về đỉnh \(t\) như sau: Tại mỗi thời điểm, chọn một đỉnh \(v\), với mỗi robot, robot có thể lựa chọn di chuyển đến \(v\) nếu có cạnh hoặc không thực hiện di chuyển. Gọi \(d(s,t)\) là thời gian ngắn nhất để hai robot cùng đến được đỉnh \(t\).

Yêu cầu: Tính tổng các giá trị \(d(s,t)\) cho mọi cặp \((s,t)\).

Input

• Dòng đầu chứa số nguyên dương \(n\) (\(n \le 500\)).
• Dòng tiếp theo chứa số nguyên dương \(m_1\) là số cạnh của đồ thị \(G_1\).
• Dòng thứ \(i\) (\(1 \le i \le m_1\)) trong \(m_1\) dòng sau, mỗi dòng chứa hai số nguyên \(x_i,y_i\) cho biết hai đỉnh \(x_i,y_i\) có cạnh nối trong đồ thị \(G_1\).
• Dòng tiếp theo chứa số nguyên dương \(m_2\) là số cạnh của đồ thị \(G_2\).
• Dòng thứ \(j\) (\(1 \le j \le m_2\)) trong \(m_2\) dòng sau, mỗi dòng chứa hai số nguyên \(u_j,v_j\) cho biết hai đỉnh \(u_j,v_j\) có cạnh nối trong đồ thị \(G_2\).

Output

• Gồm một dòng là tổng các giá trị \(d(s,t)\) cho mọi cặp \((s,t)\).

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n \le 100\).
• Subtask \(2\) (\(50\%\) số điểm): \(n \le 500\).

Example

3
3
1 2
2 3
3 1
2
1 2
2 3

8

Alice được giao thực hiện \(n\) công việc, cô đã đánh số các công việc từ \(1\) đến \(n\) và tính toán công việc thứ \(i\) (\(1 \le i \le n\)) có đặc điểm như sau:

• Thời gian thực hiện là \(t_i\).
• Mức độ quan trọng là \(w_i\) nên nếu công việc \(i\) kết thúc tại thời điểm \(d\) thì sẽ mất chi phí \(d \times w_i\).
• Công việc \(p_i\) phải được thực hiện trước công việc \(i\) (\(p_i < i\)). Chỉ có duy nhất \(p_1 = 0\) nghĩa là chỉ có công việc \(1\) có thể thực hiện ngay thời điểm \(0\) đầu tiên.

Alice cần lập lịch để tổng chi phí thực hiện cả \(n\) công việc là nhỏ nhất. Tuy nhiên, Aliec có thể thay đổi trọng số của một công việc nào đó thành \(1\).

Yêu cầu: Hãy giúp Alice tìm cách thay đổi trọng số của một công việc để chi phí thực hiện của cả \(n\) công việc là nhỏ nhất.

Input

• Dòng đầu là số nguyên dương \(n\) là số công việc.
• Dòng thứ hai gồm \(n\) số mô tả mảng \(p\).
• Dòng thứ ba gồm \(n\) số nguyên không âm mô tả mảng \(w\) (\(w_i \le 10^3\)).
• Dòng cuối cùng gồm \(n\) số nguyên không âm mô tả mảng \(t\) (\(t_i \le 10^3\)).

Output

• Một dòng chứa một số là tổng chi phí nhỏ nhất tìm được.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \le 8\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \le 18\).
• Subtask \(3\) (\(30\%\) số điểm): \(n \le 180\).
• Subtask \(4\) (\(20\%\) số điểm): \(n \le 1800\).

Example

3
0 1 1
2 3 3
1 2 3

17