회로 배치

n x n 격자판에 새 회로 하나를 배치하려고 한다. 각 칸은 격자 밖을 제외하고 상하좌우로 인접한 칸을 가진다. 회로는 인접한 칸들을 차례대로 지나는 하나의 경로이며, 시작 칸과 끝 칸이 있다.

이미 몇 개의 회로가 놓인 격자판과 새 회로의 두 끝 칸이 주어진다. 새 회로는 빈 칸뿐 아니라 이미 회로가 놓인 칸도 지날 수 있다. 빈 칸을 지나는 비용은 1이고, 이미 회로가 놓인 칸을 지나는 비용은 k이다. 시작 칸과 끝 칸의 비용도 포함하여, 새 회로가 지나는 모든 칸의 비용 합이 최소가 되도록 회로를 찾아라.

첫째 줄에 격자판의 크기 n이 주어진다. (1 <= n <= 50)

둘째 줄에 새 회로의 시작 칸과 끝 칸의 위치를 나타내는 네 정수 sr sc er ec가 주어진다. 위치는 행 번호와 열 번호 순서로 주어지며, 두 위치는 서로 다르다.

셋째 줄에 이미 회로가 놓인 칸을 지나는 비용 k가 주어진다. (2 <= k <= 60)

넷째 줄에 이미 배치된 회로의 개수 m이 주어진다. (1 <= m <= 7)

다음 m개의 줄에는 회로 하나의 정보가 주어진다. 각 줄의 첫 정수 t는 그 회로를 나타내는 점의 개수이다. (2 <= t <= 15) 이어서 시작 칸, 90도 방향 전환 칸들, 끝 칸의 위치가 r1 c1 r2 c2 ... rt ct 형식으로 주어진다. 연속한 두 점은 같은 행 또는 같은 열에 있으며, 그 사이의 모든 칸에는 이미 회로가 놓여 있다.

첫째 줄에 새 회로를 배치하는 최소 비용을 출력한다.

둘째 줄에는 최소 비용 회로의 정보를 입력의 회로 형식과 같이 출력한다. 먼저 회로를 나타내는 점의 개수 t를 출력하고, 이어서 시작 칸, 90도 방향 전환 칸들, 끝 칸의 위치를 행과 열 순서로 출력한다. 출력한 경로는 첫째 줄의 최소 비용을 달성해야 한다.