Tại một điểm bán hàng tự động, mỗi loại hàng được gán tương ứng với một số nguyên dương gọi là mã hàng, hai loại hàng khác nhau có mã hàng khác nhau. Mỗi lần khách mua hàng, máy chỉ bán một loại hàng với số lượng là ~1~ sản phẩm và ghi vào nhật kí của máy mã loại hàng đã bán. Sau khi kết thúc một đợt bán hàng, nhật kí bán hàng của máy là một dãy số nguyên dương. Người quản lí cần thống kê xem loại hàng nào đã được máy bán nhiều nhất, số lượng hàng loại đó đã bán là bao nhiêu? Bạn hãy viết chương trình giúp người quản lý tìm loại hàng đó.

Input

• Dòng đầu tiên ghi số nguyên dương ~n \le 10^4~ là số lượng hàng mà máy đã bán.
• ~N~ dòng tiếp theo mỗi dòng ghi một số nguyên dương là mã loại hàng đã bán trong nhật kí của máy. Giá trị các số nguyên dương không vượt quá ~10^6~.

Output

• In ra một dòng duy nhất ghi mã loại hàng đã bán nhiều nhất và số lượng hàng loại đó mà máy đã bán, hai giá trị này cách nhau một ký tự trống. Nếu như có nhiều loại hàng có cùng số lượng bán nhiều nhất thì in ra mã loại hàng có giá trị bé nhất.

Subtask

• Có ~60\%~ số test ứng với các giá trị mã số trong phạm vi ~[1,10^3]~.
• Có ~40\%~ số test ứng với các giá trị mã số trong phạm vị ~[1,10^6]~.

  Sample Input 1

11
1 
2 
2 
3 
2 
4 
5 
2 
6 
7 
6

Sample Output 1

2  4

Với hai số nguyên dương ~u,v~, khi viết số ~v~ sau số ~u~ ta được một số mới.

Ví dụ: ~u = 99, v = 123~, khi viết số ~v~ sau ~u~ ta thu được số mới là số ~99123~.

Cho ~n~ số nguyên dương ~a_1, a_2, a_3, ... a_n~ và ~m~ số nguyên dương ~b_1, b_2, b_3, ..., b_m~.

Yêu cầu:

• Với mỗi giá trị ~b_i~ ~(1 \le i \le m)~, bạn hãy cho biết có bao nhiêu số ~a_j~ (~1 \le j \le n~) sao cho sau khi viết ~a_j~ sau ~b_i~ ta được một số mới chia hết cho ~3~.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n,m~. (~1 \le n,m \le 10^5~).
• Dòng tiếp theo chứa ~n~ số nguyên dương miêu tả dãy ~a~. (~a_i \le 10^8, 1 \le i \le n~).
• Dòng tiếp theo chứa ~m~ số nguyên dương miêu tả dãy ~b~. (~b_i \le 10^8, 1 \le i \le m~).

Output

• Gồm ~m~ dòng, dòng thứ ~i~ ghi số lượng số ~a_j (1 \le j \le n)~ sao cho sau khi viết ~a_j~ sau ~b_i~ ta được một số mới chia hết cho ~3~.

Subtask

• Subtask ~1~ (~60\%~ số điểm): ~n,m \le 1000~
• Subtask ~2~ (~40\%~ số điểm): Không có ràng buộc gì thêm.

Sample Input 1

5  2
123  4  5  7  10
3  2

Sample Output 1

1
3

Explanation 1

~b_1 = 3~ chỉ có duy nhất một số ~a_1~ thỏa mãn. ~b_2 = 2~, có ba số ~a_2,a_4,a_5~ thỏa mãn.

Hùng vốn là pro coder ngây thơ... Vì biết Hùng pro, Nguyễn Anh Quân vốn là 1 người gặp vấn đề với số 5 đã nhờ Hùng giúp 1 câu đố liên quan đến số 5. Hùng được cho 1 xâu ~S~ độ dài ~n~, gồm các kí tự từ ~0~ đến ~9~. Hỏi từ xâu ~S~, có thể lấy bao nhiều xâu con (không cần liên tiếp), xếp lần lượt từ trái sang phải để tạo thành 1 số chia hết cho 5 (Lưu ý: các số 0 thừa ở đầu số đấy không quan trọng). Vì mới dính 1 vết sẹo, Hùng nay đã bị down và không thể làm được bài này nên đành phải nhờ các bạn 10 Tin gửi cứu.

Yêu cầu:

• Hùng muốn biết số lượng xâu con (không cần liên tiếp) của xâu ~S~ mà khi xếp lần lượt từ trái sang phải tạo thành 1 số chia hết cho 5. Hùng muốn biết con số này khi chia lấy dư cho ~10^9 + 7~.

Input

• Dòng thứ nhất chứa một số nguyên dương ~n~ (~1 \le n \le 10^6~);
• Dòng thứ hai chứa xâu ~S~ gồm các kí tự từ ~0~ đến ~9~.

Output

• In ra số lượng xâu con thỏa mãn khi chia lấy dư cho ~10^9 + 7~.

Subtask

• Subtask ~1~ (~50\%~ số điểm): ~n <= 20~
• Subtask ~2~ (~50\%~ số điểm): ~n <= 10^6~.

Sample Input 1

5
06593

Sample Output 1

5

Explanation 1

• Các xãu con thỏa mãn khi xếp lại là: ~0~, ~5~, ~05~, ~65~, ~065~.

Trên hệ trục tọa độ ~OXY~, có ~n~ con robot, con robot thứ ~i~ ở tọa độ ~(x_i,y_i)~.

Giả sử một con robot đang ở vị trí ~(x,y)~, sau một giây, nó có thể đi tới ~4~ vị trí ~(x-1,y)~, ~(x,y-1)~, ~(x+1,y)~, ~(x,y+1)~.

Hãy tìm thời điểm ngắn nhất sao cho cả ~n~ con robot đều có thể cùng đứng ở một điểm nào đó trên hệ trục tọa độ.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~ miêu tả số robot ~(1 \le n \le 3\times 10^5)~.
• ~n~ dòng sau, dòng thứ ~i~ gồm ~2~ số nguyên ~x_i,y_i~ miêu tả tọa độ ~(x_i,y_i)~ của robot thứ ~i~ ~(|x_i|,|y_i| \le 10^{18})~.

Output

• In ra thời điểm nhanh nhất để các robot cùng đứng tại một điểm.

Sample Input 1

3
0 0
0 3
3 3

Sample Output 1

3