쇼핑 잔돈

Felix와 그의 친구 M명은 오늘 쇼핑을 하며 지갑을 정리하고 있다. 최근 현금 거래로 Felix는 N장의 지폐로 된 잔돈을 받았다. Felix는 받은 지폐를 순서를 바꾸지 않고 지갑에 끼워 넣으려 한다.

예를 들어 Felix가 N = 4장의 지폐를 다음 순서로 받았다고 하자: C1 C2 C3 C4. Felix의 지갑에 W1 W2 W3 순서로 3장의 지폐가 있다면, 잔돈을 지갑에 끼워 넣는 방법은 네 가지다.

1. 첫 번째 지폐 앞에 끼워 넣는다. 끼워 넣은 후 지갑의 지폐 순서는 C1 C2 C3 C4 W1 W2 W3이다.
2. 첫 번째와 두 번째 지폐 사이에 끼워 넣는다. 끼워 넣은 후 지갑의 지폐 순서는 W1 C1 C2 C3 C4 W2 W3이다.
3. 두 번째와 세 번째 지폐 사이에 끼워 넣는다. 끼워 넣은 후 지갑의 지폐 순서는 W1 W2 C1 C2 C3 C4 W3이다.
4. 세 번째 지폐 뒤에 끼워 넣는다. 끼워 넣은 후 지갑의 지폐 순서는 W1 W2 W3 C1 C2 C3 C4이다.

Felix는 정리 정돈을 좋아하기 때문에 지갑 속 지폐가 최대한 정렬되어 있기를 바란다. 따라서 잔돈을 끼워 넣은 뒤 지갑의 반전 수가 최소가 되도록 끼워 넣으려 한다. 지갑의 반전 수란 지갑 안 지폐 쌍 (x, y) 중 다음 조건을 만족하는 쌍의 개수이다.

• 지폐 x가 지폐 y보다 앞에 있고,
• 지폐 x의 가치가 지폐 y의 가치보다 엄격하게 크다.

오늘은 좀 관대해진 Felix는 잔돈을 자신이 가지지 않고 친구 한 명에게 주고, 그 친구의 지갑에 잔돈을 끼워 넣으려 한다. i번째 친구의 지갑에는 Li장의 지폐가 있고, 그 가치는 지갑의 앞에서 뒤로 Wi[1], Wi[2], ..., Wi[Li]이다. Felix는 잔돈을 끼워 넣은 뒤 친구 지갑의 반전 수를 최소로 만들 수 있는 친구에게 잔돈을 주려 한다. 따라서 각 친구에 대해, 잔돈을 그 친구의 지갑에 끼워 넣었을 때의 최소 반전 수를 구해야 한다.

첫 줄에 두 정수 N M (1 ≤ N, M ≤ 100 000)이 주어진다. N은 잔돈의 지폐 수, M은 Felix의 친구 수이다. 다음 줄에 N개의 정수 Ci (1 ≤ Ci ≤ 109)가 주어진다. Ci는 잔돈 지폐의 가치이다. 다음 M개 줄 각각은 정수 Li (1 ≤ Li ≤ 200 000)로 시작한다. Li는 i번째 친구 지갑의 지폐 수이다. 이어서 Li개의 정수 Wi[j] (1 ≤ Wi[j] ≤ 109)가 주어진다. Wi[j]는 지갑 지폐의 가치이다. 모든 Li의 합은 200 000 이하이다.

각 친구에 대해 입력 순서대로, Felix가 그 친구의 지갑에 잔돈을 끼워 넣었을 때의 최소 반전 수를 한 줄에 하나씩 출력한다.