시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 80 7 4 80.000%

문제

종범이의 집에는 N개의 전자기기들이 있다. i번 전자기기는 Xi개의 장치로 구성되어 있고, i번 전자기기의 j번 장치는 Ai,j의 전력을 공급받아야 정상적으로 동작한다. Ai,j 미만의 전력을 공급받으면 전력이 부족해서 동작하지 않고, Ai,j 초과의 전력을 공급받으면 장치가 망가진다. i번 전자기기의 장치들 중 Yi개 이상의 장치가 정상적으로 동작하면 i번 전자기기를 사용할 수 있다. 종범이는 장치들 중 하나에 전력을 공급할 수 있는 M개의 전원 공급 장치가 있다. k번 전원 공급 장치는 Zk가지 서로 다른 전력들 중 하나를 골라 정확히 하나의 장치에 공급할 수 있으며, k번 전원 공급 장치가 공급할 수 있는 전력들 중 l번째로 작은 것은 Bk,l이다.

종범이는 새 전자기기를 들일 때마다 전원 공급 장치를 아무거나 사서 연결해 N개의 전자기기를 모두 잘 사용하고 있었다. 종범이는 이사를 할 일이 생겼고, 가지고 있는 전자기기들과 전원 공급 장치를 모두 들고 이사를 했다. 그런데 깜빡하고 어느 전자기기의 어느 장치에 어떤 전원 공급 장치를 연결했는지 기록하지 않고 이사를 해 버려 전자기기를 사용할 수 없게 되었다. 이사한 기념으로 리X오X레XX와 스타XXXX를 하려던 종범이는 전자기기를 사용할 수 없다는 사실이 너무 슬펐다. 종범이를 도와 어느 전자기기의 어느 장치에 어떤 전원 공급 장치를 연결하면 모든 전자기기를 사용할 수 있는지를 찾아주자.

입력

1행에 N이 주어진다. (1 ≤ N ≤ 100)

2행부터 2N + 1행까지 N개의 전자기기에 대한 설명이 주어진다.

  • 2i행에는 Xi와 Yi가 주어진다. (1 ≤ Yi ≤ Xi ≤ 100)
  • 2i + 1행에는 Xi개의 정수 Ai,j가 주어진다. (1 ≤ Ai,j ≤ 109)

2N + 2행에 M이 주어진다. (1 ≤ M ≤ 10, 000)

2N + 3행부터 2N + 2M + 2행까지 M개의 전원 공급 장치에 대한 설명이 주어진다.

  • 2N + 2k + 1행에는 Zk가 주어진다. (1 ≤ Zk ≤ 10)
  • 2N + 2k + 2행에는 Zk개의 정수 Bk,l이 주어진다. (1 ≤ Bk,l ≤ 109)

모든 전자기기를 사용할 수 있는 연결 방법이 하나 이상 존재함이 보장된다

출력

1행에 서로 연결해야 하는 전자기기의 장치와 전원 공급 장치의 연결 개수 W를 출력한다.

2행부터 W + 1행까지 각 행에 (i, j, k, l) 순서쌍을 출력한다. 이는 i번 전자기기의 j번 장치와 k번 전원 공급 장치를 연결하고, k번 전원 공급 장치가 공급할 수 있는 전력들 중 l번째로 작은 것을 선택해야 한다는 것을 의미한다.

한 전자기기의 장치가 여러 번 등장하거나 한 전원 공급 장치가 여러 번 등장하면 안 된다. 또한 각 연결에 대해서 전자기기의 장치가 요구하는 전력과 전원 공급 장치가 공급하는 전력의 양이 동일해야 한다.

예제 입력 1

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

예제 출력 1

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

힌트

총 5개의 연결이 있다.

1번 전자기기의 2번 장치에는 5번 전원 공급 장치로 1의 전력을 공급했고, 1번 전자기기의 3번 장치에는 1번 전원 공급 장치로 3의 전력을 공급했다. 1번 전자기기의 장치들 중 2개 이상이 동작하므로 1번 전자기기를 사용할 수 있다.

2번 전자기기의 1번 장치에는 2번 전원 공급 장치로 2의 전력을 공급했고, 2번 전자기기의 2번 장치에는 4번 전원 공급 장치로 4의 전력을 공급했고, 2번 전자기기의 4번 장치에는 3번 전원 공급 장치로 4의 전력을 공급했다. 2번 전자기기의 장치들 중 3개 이상이 동작하므로 2번 전자기기를 사용할 수 있다.