Con đường Vạn Hoa có độ dài \(m\) mà giáo sư \(x\) thường đi ngắm cảnh trong kỳ nghỉ đang vào mùa lễ hội, ngày nào cũng có \(m\) lễ hội trên đường đánh số từ 1 đến \(m\). Lễ hội thứ \(i\) diễn ra tại địa điểm cách điểm đầu của con đường một khoảng cách đúng bằng \(i\), nó được tiến hành từ thời điểm \(0\) cho tới hết thời điểm \(t_i\) trong ngày. Trong thời gian lễ hội tổ chức không xe nào được đi qua điểm diễn ra lễ hội mà phải đợi tới khi lễ hội kết thúc mới được đi qua.

Giáo sư \(X\) không quan tâm lắm tới các lễ hội mà ông chỉ đam mê tốc độ trong khung cảnh thiên nhiên hoang dã, trong mỗi ngày đi dạo (bằng mô tô) từ đầu tới cuối con đường Vạn Hoa, ông muốn tính toán xem mình có thể đi với tốc độ tối da là bao nhiêu mà không phải dừng lại chờ bát cứ lễ hội nào.

Yêu cầu: Cho biết tốc độ tối đa có thể của giáo sư \(X\) trong mỗi ngày, biết rằng kỳ nghỉ của giáo sư diễn ra trong \(n\) ngày và vào ngày thứ \(j\) giáo sư bắt đầu đi vào thời điểm \(s_j\).

Input

• Dòng 1 chứa số nguyên \(m\) (\(1 ≤ m ≤ 10^5\)).

• Dòng 2 chứa \(m\) số nguyên \(t_1, t_2, ..., t_m\), \(t_i ≤ 10^{12}\).

• Dòng 3 chứa số nguyên \(n\) (\(1 ≤ n ≤ 10^5\)).

• Dòng 2 chứa \(n\) số nguyên \(s_1, s_2, ..., s_n\), \(t_i ≤ 10^{12}\) (\(s_j < max(t_1, t_2, ..., t_m)\).

Output

Ghi ra \(n\) dòng, dòng thứ \(j\) ghi hai số nguyên \(p, q\) ứng với tử số và mẫu số của phân số tới giản \(\frac{p}{q}\) là tốc độ tối đa (tính bằng số đơn vị độ dài/một đơn vị thời gian) của giáo sư trong ngày thứ \(j\).

Sample Input

4
3 5 6 1
3
0 3 5

Sample Output

1 3
1 1
3 1