Bạn được cho một tập các vector trong mặt phẳng, các vector đều xuất phát từ gốc tọa độ. Nhiệm vụ của bạn là tìm cặp vector với số đo góc không định hướng giữa chúng là nhỏ nhất.

Góc không định hướng có giá trị trong khoảng từ ~0~ đến ~\pi~, là giá trị nhỏ nhất giữa ~2~ góc định hướng xuôi và ngược chiều kim đồng hồ. Ví dụ, ~2~ vector ngược chiều nhau có số đo góc bằng ~\pi~.

Input

• Dòng đầu chứa một số nguyên ~n~ ~(2 \le n \le 100 \, 000)~ ~-~ số lượng vector.
• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~x_i~ và ~y_i~ ~(|x|, |y| \le 10 \, 000, x^2 + y^2 > 0)~ ~-~ tọa độ của vector thứ ~i~. Các vector được đánh số từ ~1~ đến ~n~ theo thứ tự nhập vào của input. Input đảm bảo rằng không có cặp vector nào chung hướng (nhưng vẫn có thể ngược hướng).

Output

In ra hai số nguyên ~a~ và ~b~ ~(a \neq b)~ ~-~ cặp chỉ số của hai vector có số đo góc không định hướng nhỏ nhất. Bạn có thể in hai số đó theo thứ tự bất kỳ. Nếu có nhiều kết quả, in ra cặp số bất kì trong các kết quả đó.

Sample 1

Input

4
-1 0
0 -1
1 0
1 1

Output

3 4

Sample 2

Input

6
-1 0
0 -1
1 0
1 1
-4 -5
-4 -6

Output

6 5

Igor đang tham quan bảo tàng và anh ấy muốn được chiêm ngưỡng nhiều bức tranh nhất có thể.

Bảo tàng được biểu diễn dưới dạng hình chữ nhật kích thước ~n \times m~ ô. Mỗi ô có thể trống hoặc không thể đi qua. Các ô trống được đánh dấu là ., các ô không thể đi qua được đánh dấu là *. ~2~ ô khác loại kề nhau (~1~ trống và ~1~ không thể đi qua) được ngăn cách bởi bức tường chứa ~1~ bức tranh.

Ban đầu Igor đang đứng ở một ô trống nào đó. Tại mỗi thời điểm anh ấy có thể di chuyển sang một ô trống khác kề với ô hiện tại.

Cho trước một số ô xuất phát, với mỗi ô, hãy tính số lượng bức tranh tối đa mà Igor có thể chiêm ngưỡng. Igor chỉ có thể xem tranh khi anh ấy đứng tại vị trí kề bức tường chứa bức tranh đó. Igor có rất nhiều thời gian, vậy nên anh ấy sẽ chiêm ngưỡng các bức tranh mà mình có thể thấy.

Input

• Dòng đầu tiên chứa ba số nguyên ~n~, ~m~ và ~k~ ~(3 \le n, m \le 1000, 1 \le k \le min(n \cdot m, 100\,000))~ ~-~ các kích thước của bảo tàng và số lượng ô xuất phát.

• ~n~ dòng tiếp theo, mỗi dòng chứa ~m~ kí tự ., * mô tả bảo tàng. Input đảm bảo rằng các ô ở biên đều không thể đi qua, tránh trường hợp Igor đi ra khỏi bảo tàng.

• ~k~ dòng cuối cùng, mỗi dòng chứa hai số nguyên ~x~ và ~y~ ~(1 \le x \le n, 1 \le y \le m)~ ~-~ một trong các ô xuất phát của Igor. Các dòng được đánh số từ trên xuống dưới, các cột ~-~ từ trái qua phải. Input đảm bảo các vị trí xuất phát đều là ô trống.

Output

In ra trên ~k~ dòng ~-~ số bức tranh tối đa mà Igor có thể chiêm ngưỡng, nếu Igor xuất phát tại ô tương ứng.

Sample 1

Input

5 6 3
******
*..*.*
******
*....*
******
2 2
2 5
4 3

Output

6
4
10

Sample 2

Input

4 4 1
****
*..*
*.**
****
3 2

Output

8

Bạn có một thanh sô-cô-la hình chữ nhật chứa ~n \times m~ ô vuông. Bạn muốn ăn chính xác ~k~ ô sô-cô-la, vì vậy bạn phải tìm cách bẻ thanh sô-cô-la này ra.

Trong một thao tác, bạn có thể chọn và bẻ một thanh sô-cô-la hình chữ nhật thành hai thanh hình chữ nhật nhỏ hơn. Bạn chỉ có thể bẻ theo các đường thẳng giữa các ô vuông: theo chiều dọc hoặc theo chiều ngang. Chi phí cho thao tác sẽ bằng bình phương độ dài cần bẻ.

Ví dụ, nếu bạn có một thanh sô-cô-la chứa ~2 \times 3~ ô vuông, thì bạn có thể bẻ theo chiều ngang và được hai thanh ~1 \times 3~ (chi phí cho thao tác này là ~3^2 = 9~), hoặc bạn có thể bẻ theo chiều dọc ở một trong hai vị trí và được hai thanh: ~2 \times 1~ và ~2 \times 2~ (chi phí cho thao tác này là ~2^2 = 4~).

Cho các giá trị ~n, m, k~, hãy tìm tổng chi phí nhỏ nhất để bẻ thanh sô-cô-la. Bạn có thể ăn đúng ~k~ ô sô-cô-la nếu sau khi thực hiện các thao tác bẻ, tồn tại một tập hợp các thanh sô-cô-la hình chữ nhật mà chứa tổng cộng ~k~ ô vuông. Ngoài ra, ~nm-k~ ô vuông còn lại không nhất thiết phải thuộc cùng một thanh hình chữ nhật.

Input

Dòng đầu tiên chứa một số nguyên ~t~ ~(1 \leq t \leq 40910)~ - số lượng bộ dữ liệu cần xử lí.

Mỗi dòng trong ~t~ dòng tiếp theo chứa ba số nguyên ~n, m, k~ ~(1 \leq n, m \leq 30, 1 \leq k \leq min(nm, 50))~ - lần lượt là kích thước của thanh sô-cô-la và số ô vuông sô-cô-la mà bạn muốn ăn.

Output

Với mỗi bộ dữ liệu, in ra chi phí nhỏ nhất cho việc bẻ thanh sô-cô-la để ăn được chính xác ~k~ ô vuông.

Sample Input

4
2 2 1
2 2 3
2 2 2
2 2 4

Sample Output

5
5
4
0

Note

Ở truy vấn đầu tiên, ta có thể thực hiện hai thao tác bẻ:

• Bẻ thanh ~2 \times 2~ thành hai thanh ~2 \times 1~ (chi phí ~2^2 = 4~),
• Bẻ một thanh ~2 \times 1~ vừa nhận được, thành hai thanh ~1 \times 1~ (chi phí ~1^2 = 1~).

Ở truy vấn thứ hai, để ăn ~3~ ô thì ta cũng có thể thực hiện thao tác tương tự như truy vấn đầu tiên.

Cho một đa giác ~n~ điểm và không tự cắt chính nó. Đa giác có thể không lồi và có thể chứa góc ~180~ độ.

Cho ~m~ đường thẳng. Với mỗi đường thẳng, hãy tìm độ dài của phần chung giữa đường thẳng đó và đa giác đã cho.

Input

Dòng đầu tiên chứa các số nguyên ~n~ và ~m~ ~(3 \le n \le 1000; 1 \le m \le 100)~.

~n~ dòng tiếp theo, mỗi dòng ghi toạ độ các điểm của đa giác (theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ). Các điểm phân biệt với nhau.

~m~ dòng tiếp theo, mỗi dòng gồm toạ độ hai điểm phân biệt trên đường thẳng, mô tả đường thẳng đó.

Mọi toạ độ trong input đều là số thực với tối đa ~2~ chữ số ở phần thập phân. Ngoài ra, các toạ độ này có giá trị tuyệt đối không quá ~10^5~.

Output

In ra ~m~ dòng, dòng thứ ~i~ chứa độ dài của phần chung giữa đường thẳng thứ ~i~ và đa giác. Đáp án sẽ được tính là đúng nếu sai số không vượt quá ~10^{-6}~.

Sample Input

4 3
0 0
1 0
1 1
0 1
0 0 1 1
0 0 0 1
0 0 1 -1

Sample Output

1.41421356237309514547
1.00000000000000000000
0.00000000000000000000

Một xâu được gọi là xâu đối xứng nếu nó đọc giống nhau từ trái sang phải và từ phải sang trái. Ví dụ: kazak, oo, r và mikhailrubinchikkihcniburliahkim là xâu đối xứng, nhưng xâu abb và ij thì không.

Bạn được cho xâu ~s~ bao gồm các chữ cái Latinh viết thường. Mỗi lần biến đổi, bạn có thể chọn bất kỳ một vị trí nào trong xâu rồi thay đổi chữ cái ở vị trí đó thành bất kỳ chữ cái Latinh thường nào khác và độ dài của xâu là không đổi. Bạn cũng có thể hoán vị thứ tự của các chữ cái trong xâu một cách tùy ý. Chú ý rằng hoán vị không được tính là một phép biến đổi.

Hãy tính số lần biến đổi tối thiểu để xâu ~s~ trở thành một xâu đối xứng. Nếu sau số lần biến đổi tối thiểu ấy có nhiều xâu ~s~ thỏa mãn, in ra xâu có thứ tự từ điển nhỏ nhất.

Input

Dòng duy nhất chứa xâu ~s~ ~(1 \le |s| \le 2\cdot 10^5)~ gồm các chữ cái Latinh viết thường.

Output

In ra xâu đối xứng có thứ tự từ điển nhỏ nhất có thể nhận được sau số lần biến đổi tối thiểu.

Sample 1

Input

aabc

Output

abba

Sample 2

Input

aabcd

Output

abcba

Trường X muốn xây một sân khấu với mặt sân có dạng hợp của hai hình tròn giao nhau (hai hình tròn có thể không giao nhau do bản thiết kế bị lỗi). Bán kính của hai hình tròn lần lượt là ~r_1~ mét và ~r_2~ mét. Coi sân trường là một hệ trục tọa độ thì tâm của hai hình tròn có tọa độ là ~(x_1, y_1)~, ~(x_2, y_2)~. Chi phí làm mỗi ~m^2~ mặt sân phần giao của hai hình tròn khác với phần còn lại. Hãy tính diện tích giao nhau hai hình tròn để giúp trường dự trù kinh phí.

Input

• Dòng đầu tiên chứa ~3~ số nguyên ~x_1,\ y_1,\ r_1~ ~(-10^9 \le x_1, y_1 \le 10^9,\ 1 \le r_1 \le 10^9)~ - vị trí tâm và bán kính của đường tròn thứ nhất.
• Dòng thứ hai chứa ~3~ số nguyên ~x_2,\ y_2,\ r_2~ ~(-10^9 \le x_2, y_2 \le 10^9,\ 1 \le r_2 \le 10^9)~ - vị trí tâm và bán kính của đường tròn thứ hai.

Output

In ra diện tích phần giao nhau của hai hình tròn. Đáp án sẽ được coi là đúng nếu sai số tuyệt đối hoặc tương đối không vượt quá ~10^{-6}~.

Sample 1

Input

0 0 4
6 0 4

Output

7.25298806364175601379

Sample 2

Input

0 0 5
11 0 5

Output

0.00000000000000000000

Cho một cây không trọng số, có gốc là đỉnh ~1~. Mỗi đỉnh sẽ được tô bằng một màu.

Gọi màu ~c~ là phổ biến trong cây con gốc ~v~ nếu như không tồn tại màu nào khác xuất hiện trong cây con gốc ~v~ nhiều lần hơn hơn màu ~c~. Do đó có thể có nhiều hơn hai màu phổ biến trong một cây con nào đó.

Cây con gốc ~v~ bao gồm đỉnh ~v~ và các đỉnh chứa đỉnh ~v~ trên đoạn đường tới gốc.

Với mỗi đỉnh ~v~, hãy tìm tổng các màu phổ biến xong cây con gốc ~v~.

Input

Dòng thứ nhất chứa một số nguyên ~n~ ~(1 \le n \le 10^5)~ - là số đỉnh trong cây.

Dòng thứ hai gồm ~n~ số nguyên ~c_1, c_2, \ldots, c_n~ ~(1 \le c_i \le n)~ với ~c_i~ là màu của đỉnh thứ ~i~.

~n - 1~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~x_j, y_j~ ~(1 \le x_j, y_j \le n)~ - là một cạnh của cây.

Output

In ra ~n~ số nguyên trên một dòng với số thứ ~i~ là tổng các màu phổ biến trong cây con gốc ~i~.

Sample 1

Input

4
1 2 3 4
1 2
2 3
2 4

Output

10 9 3 4

Sample 2

Input

15
1 2 3 1 2 3 3 1 1 3 2 2 1 2 3
1 2
1 3
1 4
1 14
1 15
2 5
2 6
2 7
3 8
3 9
3 10
4 11
4 12
4 13

Output

6 5 4 3 2 3 3 1 1 3 2 2 1 2 3

Cho một đồ thị hai phía vô hướng và không có cạnh trùng. Hãy tô màu các cạnh của đồ thị với số lượng màu tối thiểu, sao cho hai cạnh kề nhau được tô bằng hai màu khác nhau.

Input

Dòng đầu tiên gồm ba số nguyên ~a, b~ và ~m~ ~(1 \le a, b \le 1000, 0 \le m \le 10^5)~ với ~a~ là số đỉnh của phần thứ nhất, ~b~ là số đỉnh của phần thứ hai, và ~m~ là số cạnh trong đồ thị.

~m~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~x~ và ~y~ ~(1 \le x \le a, 1 \le y \le b)~ thể hiện một cạnh trong đồ thị với ~x~ là thứ tự của đỉnh trong phần thứ nhất, và ~y~ là thứ tự của đỉnh trong phần thứ hai. Đảm bảo đồ thị sẽ không có cạnh trùng.

Output

Dòng đầu tiên in ra một số nguyên ~c~ là số lượng màu tối thiểu cần.

Dòng thứ hai in ra ~m~ số nguyên trong khoảng ~[1, c]~ là màu của các cạnh theo thứ tự input đã cho.

Nếu có nhiều đáp án, hãy in ra một trong số chúng.

Sample

Input

4 3 5
1 2
2 2
3 2
4 1
4 3

Output

3
1 2 3 1 2

Giải thích

Một cách tô màu là như sau:

với màu vàng là ~1~, màu xanh lá là ~2~, và màu đỏ là ~3~.

Phòng máy tính của trường có ~n~ máy chủ chịu trách nhiệm xử lý một số tác vụ tính toán. Bạn biết số lượng nhiệm vụ đã lên lịch cho mỗi máy chủ: có ~m_i~ nhiệm vụ được giao cho máy chủ thứ ~i~.

Để cân bằng tải cho từng máy chủ, bạn muốn chỉ định lại một số nhiệm vụ để hiệu số nhiệm vụ giữa máy chủ tải nhiều nhất và máy chủ tải ít nhất là nhỏ nhất. Nói cách khác, bạn muốn biểu thức ~m_a - m_b~ là nhỏ nhất, trong đó ~a~ là máy chủ được tải nhiều nhất và ~b~ là máy chủ tải ít nhất.

Trong một giây, bạn chỉ có thể giao lại một nhiệm vụ. Vì vậy, trong một giây, bạn có thể chọn bất kỳ một cặp máy chủ nào và di chuyển một nhiệm vụ từ máy chủ này sang máy chủ còn lại.

Viết chương trình tìm số giây tối thiểu để cân bằng tải giữa các máy chủ.

Input

Dòng đầu tiên chứa số dương ~n~ ~(1 ≤ n ≤ 10^5)~ - số lượng máy chủ.

Dòng thứ hai chứa chuỗi các số nguyên không âm ~m_1, m_2, ..., m_n~ ~(0 ≤ m_i ≤ 2 \times 10^4)~, trong đó ~m_i~ là số tác vụ được giao cho máy chủ thứ ~i~.

Output

In số giây tối thiểu để cân bằng tải.

Sample 1

Input

2
1 6

Output

2

Sample 2

Input

7
10 11 10 11 10 11 11

Output

0

Sample 3

Input

5
1 2 3 4 5

Output

3

Giải thích

Ví dụ 1: Trong mỗi giây, một tác vụ từ máy chủ số ~2~ sẽ được chuyển sang máy chủ số ~1~. Sau hai giây, sẽ có ~3~ nhiệm vụ trên máy chủ số ~1~ và ~4~ tác vụ trên máy chủ số ~2~.

Ví dụ 2: Tải đã được cân bằng.

Ví dụ 3:

1. Chuyển một nhiệm vụ từ máy chủ số ~4~ sang máy chủ số ~1~ (dãy ~m~ trở thành: ~2~ ~2~ ~3~ ~3~ ~5~);
2. Chuyển một nhiệm vụ từ máy chủ số ~5~ sang máy chủ số ~1~ (dãy ~m~ trở thành: ~3~ ~2~ ~3~ ~3~ ~4~);
3. Chuyển một nhiệm vụ từ máy chủ số ~5~ sang máy chủ số ~2~ (dãy ~m~ trở thành: ~3~ ~3~ ~3~ ~3~ ~3~).

Trình tự trên là một trong số các cách khả thi để cân bằng tải của các máy chủ trong ba giây.

Ở hội chợ, người ta rao bán ~m~ món đồ chơi. Các món được đánh số lần lượt là: ~1, 2, ..., m~.

Nura muốn mua ~k~ món đồ chơi trong số đó, tuy nhiên bạn ấy chỉ có ~s~ VND (đồng Việt Nam) trong túi. Để mua các món đồ chơi này, Nura cần trả bằng đồng đô la (loại ~1~) hoặc bảng (loại ~2~). Món đồ thứ ~i~ được bán theo loại tiền ~t_i~ với giá ~c_i~.

Nura có thể mua các món đồ chơi này trong ~n~ ngày ~(1, 2, ..., n)~. Mỗi ngày, bạn ấy sẽ được biết thông tin về tỉ giá để đổi VND sang đô la và bảng. Tức là, với mỗi ngày, Nura biết được rằng ~1~ đô bằng bao nhiêu VND và ~1~ bảng bằng bao nhiêu VND.

Từ ngày ~1~ đến ~n~, mỗi ngày Nura có thể chọn mua một số món đồ chơi với tỉ giá của ngày tương ứng. Bạn ấy có thể mua bao nhiêu tuỳ thích, tuy nhiên mỗi món trong ~m~ món chỉ được mua đúng ~1~ lần trong ~n~ ngày.

Hãy giúp Nura mua được ~k~ món đồ chơi sớm nhất có thể (ngày đầu tiên Nura có đủ ~k~ món đồ là ngày có chỉ số nhỏ nhất). Biết rằng, Nura chỉ có tiền VND, và phải chuyển đổi tiền VND sang đô la hoặc bảng để mua các món đồ chơi đó.

Input

Dòng đầu tiên chứa bốn số nguyên ~n, m, k, s~ ~(1 \le n \le 2.10^5, 1\le k \le m \le 2.10^5, 1 \le s \le 10^9)~, lần lượt là số ngày, số lượng món đồ chơi được rao bán, số lượng món đồ Nura cần mua, số tiền (VND) mà Nura có.

Dòng thứ hai chứa ~n~ số nguyên ~a_i~ ~(1 \le a_i \le 10^6)~, có ý nghĩa: ~1~ đô bằng ~a_i~ VND vào ngày thứ ~i~.

Dòng thứ ba chứa ~n~ số nguyên ~b_i~ ~(1 \le b_i \le 10^6)~, có ý nghĩa: ~1~ bảng bằng ~b_i~ VND vào ngày thứ ~i~.

~m~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~t_i, c_i~ ~(1 \le t_i \le 2, 1 \le c_i \le 10^6)~ - loại tiền mà món đồ thứ ~i~ được bán và giá trị của nó (theo loại tiền mà nó được bán). Nhắc lại, ~t_i = 1~ tương ứng với tiền đô, và ~t_i = 2~ tương ứng với tiền bảng.

Output

Nếu Nura không thể mua đủ ~k~ món đồ chơi, in ra -1.

Ngược lại, dòng đầu tiên chứa số nguyên ~d~ - chỉ số ngày sớm nhất mà Nura có đủ ~k~ món đồ chơi. Mỗi dòng trong ~k~ dòng tiếp theo, in ra hai số nguyên ~q_i, d_i~ - chỉ số của món đồ chơi được mua và ngày mà nó được mua. Các giá trị ~q_i~ phải phân biệt, tuy nhiên các giá trị ~d_i~ có thể trùng nhau (vì Nura có thể chọn mua nhiều món trong cùng một ngày).

Nếu có nhiều phương án, in ra phương án bất kì.

Sample 1

Input

5 4 2 2
1 2 3 2 1
3 2 1 2 3
1 1
2 1
1 2
2 2

Output

3
1 1
2 3

Sample 2

Input

4 3 2 200
69 70 71 72
104 105 106 107
1 1
2 2
1 2

Output

-1

Sample 3

Input

4 3 1 1000000000
900000 910000 940000 990000
990000 999000 999900 999990
1 87654
2 76543
1 65432

Output

-1

Cho đồ thị chứa ~n~ đỉnh ~m~ cạnh, là đồ thị vô hướng có trọng số với các cạnh không chứa khuyên, ví dụ như cạnh ~(u,u)~ là một khuyên.

Với mỗi cạnh ~(u, v)~, hãy tìm trọng số nhỏ nhất có thể của cây khung chứa cạnh ~(u, v)~. Nói cách khác, ta cần tìm trọng số của cây khung nhỏ nhất chứa cạnh ~(u,v)~.

Trọng số của cây khung là tổng trọng số của tất cả các cạnh có trong cây khung.

Input

Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ ~(1 ≤ n ≤ 2 \times 10^5,~ ~n - 1 ≤ m ≤ 2 \times 10^5)~ - số đỉnh và số cạnh trong đồ thị.

Mỗi dòng trong số ~m~ dòng tiếp theo chứa ba số nguyên ~u_i, v_i, w_i~ ~(1 ≤ u_i, v_i ≤ n, u_i ≠ v_i, 1 ≤ w_i ≤ 10^9)~ - lần lượt là hai đỉnh và trọng số của cạnh thứ ~i~.

Output

In ra ~m~ dòng. Dòng thứ ~i~ chứa trọng số của cây khung nhỏ nhất chứa cạnh thứ i.

Các cạnh được đánh số từ ~1~ đến ~m~ theo thứ tự xuất hiện trong đầu vào.

Sample Input

5 7
1 2 3
1 3 1
1 4 5
2 3 2
2 5 3
3 4 2
4 5 4

Sample Output

9
8
11
8
8
8
9

Có ~n~ chú ếch đang ngồi trên trục tọa độ ~Ox~. Với mỗi chú ếch, ta biết hai giá trị ~x_i~ và ~t_i~ lần lượt là vị trí ngồi và độ dài lưỡi ban đầu của chú ếch thứ ~i~. ~m~ con muỗi sẽ lần lượt hạ cạnh xuống trục ~Ox~. Với mỗi con muỗi, ta biết hai giá trị ~p_j~ và ~b_j~ lần lượt là vị trí hạ cánh và độ lớn của con muỗi thứ ~j~. Các chú ếch và muỗi có thể được biễu diễn bằng các điểm trên trục tọa độ.

Một chú ếch có thể ăn một con muỗi nếu như con muỗi ở cùng vị trí với chú ếch hoặc ở phía bên phải với khoảng cách giữa chú ếch và con muỗi không lớn hơn độ dài lưỡi của chú ếch đó.

Nếu tại cùng một thời điểm, nhiều chú ếch có thể ăn được một con muỗi, thì chú ếch ở vị trí trái nhất sẽ ăn nó (chú ếch có giá trị ~x_i~ bé nhất). Sau khi ăn một con muỗi, độ dài lưỡi của một chú ếch sẽ tăng đúng bằng độ lớn của con muỗi đó. Sau đó, chú ếch sẽ ăn những con muỗi khác nếu như có thể (chưa bị ăn trong các lượt trước đó).

Với mỗi chú ếch, hãy in ra hai giá trị - số lượng con muỗi đã ăn và độ dài lưỡi sau khi tất cả con muỗi đã hạ cánh và không còn con muỗi nào trên trục tọa độ có thể bị ăn.

Những con muỗi sẽ hạ cánh xuống trục tọa theo thứ tự của input. Mỗi con muỗi sẽ chỉ hạ cánh sau khi tất cả con muỗi đã hạ cạnh trước đó đã bị ăn hoặc không thể bị ăn.

Input

Dòng đầu tiên gồm hai số nguyên ~n, m\,(1 \le n, m \le 2 \times 10^5)~ lần lượt là số chú ếch và số con muỗi.

~n~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~x_i, t_i\,(0 \le x_i, t_i \le 10^9)~ lần lượt là vị trí và độ dài lưỡi ban đầu của chú ếch thứ ~i~. Input đảm bảo không có hai chú ếch nào sẽ ngồi ở cùng một vị trí.

~m~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~p_j, b_j\,(0 \le p_j, b_j \le 10^9)~ lần lượt là vị trí và độ lớn của con muỗi thứ ~j~.

Output

In ra ~n~ dòng, dòng thứ ~i~ gồm hai số nguyên lần lượt là số con muỗi mà chú ếch thứ ~i~ ăn được và độ dài cuối cùng của lưỡi của của chú ếch thứ ~i~.

Sample 1

Input

4 6
10 2
15 0
6 1
0 1
110 10
1 1
6 0
15 10
14 100
12 2

Output

3 114
1 10
1 1
1 2

Sample 2

Input

1 2
10 2
20 2
12 1

Output

1 3