Cho dãy \(a\) gồm \(n\) số nguyên.

Bạn phải trả lời \(q\) truy vấn, mỗi truy vấn cho hai số nguyên \(b,c\), bạn cần tìm số cặp \((i,j)\) thoả mãn:

• \(1 \le i < j \le n\).
• \(a_i + a_j = b\).
• \(a_i \times a_j = c\).

Input

• Dòng thứ nhất chứa một số nguyên dương \(n\) (\(1 \le n \le 2 \times 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,...,a_n\) (\(1 \le |a_i| \le 10^9\)).
• Dòng thứ ba chứa một số nguyên dương \(q\) (\(1 \le q \le 2 \times 10^5\)).
• \(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(b,c\) mô tả một truy vấn (\(1 \le |b| \le 2 \times 10^9, 1 \le |c| \le 10^{18}\)).

Output

• Với mỗi truy vấn, đưa ra trên một dòng một số nguyên là kết quả của truy vấn đó.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \le 10^3, q = 1\).
• Subtask \(2\) (\(20\%\) số điểm): \(|a_i| \le 10^6, |c| \le 10^9\).
• Subtask \(3\) (\(20\%\) số điểm): \(|c| \le 10^9\).
• Subtask \(4\) (\(20\%\) số điểm): \(a_i\) phân biệt từng đôi một.
• Subtask \(5\) (\(20\%\) số điểm): không có ràng buộc gì thêm.

Example

3
1 3 2
1
3 2

1

Hôm nay là ngày sinh nhật của Bob, mẹ của Bob tặng cho cậu một xâu \(s\). Thích thú với món quà trên tay, Bob liền chạy đi tìm Alice để chơi trò xoá xâu.

Luật chơi: Mỗi lượt, một người được chọn \(2\) kí tự liên tiếp giống nhau và xoá chúng ra khỏi xâu \(s\). Người nào không thực hiện được thao tác xoá sẽ bị xử thua.

Vì là xâu của Bob nên Bob đương nhiên sẽ được đi trước. Hãy tính toán xem nếu như Bob và Alice đều chơi tối ưu, thì ai sẽ là người chiến thắng?

Input

• Một dòng duy nhất là xâu \(s\) (Độ dài của xâu \(s \le 10^5\)) chỉ chứa các chữ cái từ a đến z.

Output

• Gồm một xâu duy nhất là Bob hoặc Alice tương ứng với người chiến thắng.

Scoring

• Subtask \(1\) (\(16\%\) số điểm): Xâu \(s\) chỉ chứa duy nhất một loại kí tự.
• Subtask \(2\) (\(84\%\) số điểm): không có ràng buộc gì thêm.

Example

abacaba

Alice

iiq

Bob

Lớp của Thuận tổ chức đi chơi du lịch đến Nha Trang. Khi đến Nha Trang, họ có một buổi chiều tắm biển rất vui vẻ. Sau khi chơi vui vẻ, họ quyết định trở về khách sạn. Đoạn đường từ biển về khách sạn có độ dài là \(l\) mét. Mỗi người đều có thể đi bộ với vận tốc là \(v_{1}\) mét mỗi giây. Tuy nhiên, do đã chơi cả chiều nên ai cũng thấm mệt, họ quyết định gọi xe để trở về khách sạn. Xe có thể chở tối đa \(k\) người trong cùng một thời điểm và có vận tốc là \(v_{2}\) mét mỗi giây. Mọi người sẽ chia nhau lên xe và đi bộ, tuy nhiên mỗi người sẽ chỉ lên xe nhiều nhất một lần.

Hãy xác định khoảng thời gian ngắn nhất để tất cả \(n\) người đều trở về được khách sạn, coi khoảng thời gian lên xe và xuống xe là ngay lập tức và ta có thể bỏ qua khoảng thời gian này.

Input

• Một dòng chứa năm số nguyên \(n, l, v_{1}, v_{2}, k\) \((1 \leq n \leq 2 \times 10^{5}, 1 \leq l \leq 10^{9}, 1 \leq v_{1} < v_{2} \leq 10^{9}, 1 \leq k \leq n)\).

Output

• Đưa ra một số thực là khoảng thời gian ngắn nhất (tính theo giây) để cả \(n\) người đều trở về được khách sạn. Sai số tối đa cho phép là \(10^{-6}\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(k = n\).
• Subtask \(2\) (\(30\%\) số điểm): \(\left\lceil \frac{n}{2} \right\rceil \leq k \leq n\).
• Subtask \(3\) (\(40\%\) số điểm): không có ràng buộc gì thêm.

Example

5 10 2 4 5

2.5