Con đường Vạn Hoa độ 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\) tới \(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 đa 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 dương \(m \leq 10^5\)
• Dòng 2 chứa \(m\) số nguyên dương \(t_1, t_2, ..., t_m \leq 10^{12}\) cách nhau ít nhất một dấu cách
• Dòng 3 chứa số nguyên dương \(n \leq 10^5\)
• Dòng 4 chứa \(n\) số nguyên không âm \(s_1, s_2, ..., s_n\) cách nhau ít nhất một dấu cách (\(\forall j: s_j < \max\limits_{i=1,2,...,m} \{t_i\}\))

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\).

Example

4
3 5 6 1
3
0 3 5

1 3
1 1
3 1