Starship-Planet의 대도시 새롬시에는 10억 개의 가로 도로와 10억 개의 세로 도로가 있다. 당신은 편의상 각 가로 도로와 세로 도로에 각각 순서대로 1~10억의 번호를 매기고, A번 가로 도로와 B번 세로 도로가 만나는 교차로를 (A, B)라고 정했다. 이웃한 두 도로 사이의 거리는 같기 때문에, 이웃한 두 도로 사이를 평범한 방법으로 이동한다면 도달 시간은 1로 일정하다.

수학 연구원 Dr.Y가 당신에게 수학 물질(수학 물질이 뭔지에 대해서는 의심스럽지만 일단 넘어가자) 배달을 의뢰하였다. 각 의뢰마다, (P, Q)에 있는 수학 물질을 (R, S)로 옮겨야 한다. 매 의뢰마다, Dr.Y는 당신을 (P, Q)로 바로 보내주기 때문에 (P, Q)로 가는 데 걸리는 시간은 무시해도 좋다.

당신은 연구원만 왕래할 수 있는 N개의 비밀 통로에 대해서 출입을 허가받았다. 각 비밀 통로는 (Pk, Qk)와 (Rk, Sk)를 연결한다. 이 비밀 통로를 이용해서 두 지점 사이를 자유롭게 왕래할 수 있으며, 이 때 1의 시간이 걸린다.

수학 물질을 빨리 배달하지 않으면 그 수학 물질에 의해 머리가 아플 수 있기 때문에, 가능한 빨리 배달하려고 한다. Dr.Y의 각 의뢰에 대해서 그 의뢰를 수행할 때 걸리는 최소 시간을 구하는 프로그램을 작성하여라. 단, 한 교차로에 두 개 이상의 비밀 통로가 있을 수 있다.

입력

• 첫 번째 줄에는 비밀 통로의 수 N과 Dr.Y의 의뢰의 수 Y가 주어진다. (1 ≤ N ≤ 150, 1 ≤ Y ≤ 300)
• 두 번째 줄부터 N개의 줄에는 각 비밀 통로의 두 끝점의 위치를 나타내는 자연수 Pk, Qk, Rk, Sk 가 주어진다. (1 ≤ Pk, Qk, Rk, Sk ≤ 10억)
• N+2번째 줄부터 Y개의 줄에는 Dr.Y의 각 의뢰에 대하여 시작점의 좌표 P, Q와 도착점의 좌표 R, S가 주어진다. (1 ≤ P, Q, R, S ≤ 10억)

출력

입출력 예

입력

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

출력

4
11
3
4

예제 설명

1번째 의뢰 : (2, 1) -> (3, 2) -> (4, 5) -> (5, 5) 로 가면 4의 시간이 걸린다.
2번째 의뢰 : (9, 1) -> (5, 1) -> (2, 4) -> (1, 9) 로 가면 11의 시간이 걸린다.
3번째 의뢰 : (1, 2) -> (1, 3) -> (5, 3) -> (4, 3) 으로 가면 3의 시간이 걸린다.
4번째 의뢰 : (3, 4) -> (5, 6) 으로 평범하게 가면 4의 시간이 걸린다.

출처:functionx