Біметалеві монети складаються з двох деталей: золотого обідка та срібної вставки. Банк Анчурії має \(n\) типи срібних вставок і \(m\) типи золотих обідків. Монета може бути зібрана з будь-якої пари (ободок, вставка). Кожна деталь має номінал; номінал отриманої монети дорівнює сумі номіналів складових її деталей.

Король Анчурії хоче дізнатися, скільки різних номіналів монет може випустити банк, і для кожного номіналу - кількість різних монет цього номіналу (монети вважаються різними, якщо вони відрізняються хоча б однією деталлю).

Формат вхідних даних

Перший рядок входу містить одне ціле число \(n\) (\(1 \le n \le 100000\)) --- кількість типів срібних вставок. Другий рядок містить \(n\) цілих чисел --- номінали вставок (всі ці числа попарно різні).

Третій рядок містить одне ціле число \(m\) (\(1 \le m \le 100000\)) --- кількість типів золотих обідків. Четвертий рядок містить \(m\) цілих чисел --- номінали обідків (всі ці числа також попарно різні).

Усі номінали додатні і не перевищують 100000.

Формат вихідних даних

Виведіть для кожного номіналу в окремому рядку два цілих числа: сам номінал і кількість різних монет даного номіналу. Номінали при цьому повинні бути впорядковані за зростання.

Приклад вхідних даних

3
1 2 3
2
2 4

Приклад вихідних даних

3 1
4 1
5 2
6 1
7 1

Примітка

Нижче для кращого розуміння теми наведено дві реалізації БПФ:

• стандартна, рекурсивна реалізація;
• покращена реалізація, без рекурсії в явному вигляді (на практиці працює в 3-4 рази швидше за звичайну).