Online Quiz System

Time limit8sMemory limit512 MB

Summary

Given per-player delays and each player's answer timing, simulate the polling protocol and report bytes sent and received by the server and each player.

Level: Hard8 of 10
Topics: Simulation, Implementation, Sorting, Array
Solved: No attempts yet

Problem

A quiz service runs on the Internet with one server and $M$ players. The bandwidth given to the server is small, so the protocol has to move as few bytes as possible, and every player has to stay synchronized while a quiz session is running. Simulate the packets that the clients and the server exchange during one game and report how much data each side moves.

A game runs like this. The participating players and the problems are fixed in advance. Every player runs the same client and has already downloaded the problem statements, so that part is not simulated. The game then begins. The first problem is presented, the players answer it within a fixed amount of time, the second problem is presented, and so on. When every problem is finished, the game ends. During a problem phase each player is told what the other players have done. Before you submit your own answer you learn who has already submitted, and after you submit you also learn which answers the others sent.

When a problem phase starts, the server sends a synchronization packet for problem-start to every player and starts polling. At every multiple of 1,000 milliseconds after the start of polling, the server checks whether any answer arrived strictly before that moment and has not been reported yet. If at least one such answer exists, the server sends a notification to every player.

A player whose answer the server has not received yet gets notification packet type A, listing the newly received answers.
A player whose own answer is among the newly received ones gets notification packet type B, listing every answer submitted by another player that arrived strictly before that moment, that is, every such answer except this player's own.
A player whose answer was already reported at an earlier check gets notification packet type B, listing the newly received answers.
A notification packet of either type has to carry information about at least one player. When it would carry none, the server does not send it.

20,000 milliseconds after the synchronization packet for problem-start, the server runs the same check one last time, sends the notification packets it needs to send, and then sends a synchronization packet for problem-end to every player, which ends the problem.

A player may answer after receiving the synchronization packet for problem-start and before receiving the synchronization packet for problem-end. An answer is sent in an answer packet.

The one-way delay between player $i$ and the server is $D_i$ milliseconds. A packet the server sends at time $t$ reaches player $i$ at time $t + D_i$ , and a packet player $i$ sends at time $t$ reaches the server at time $t + D_i$ .

The packets have the layouts below, with every size in bytes.

Table 1: synchronization packet for problem-start

Content	Size
packet header	3

Table 2: answer packet

Content	Size
packet header	3
player ID	1
answer data size ( $= L$ )	1
answer data	$L$

Table 3: notification packet type A describing others' answers

Content	Size
packet header	3
number of other players' answers ( $= N$ )	1
the next row repeats $N$ times
player ID	1

Table 4: notification packet type B describing others' answers

Content	Size
packet header	3
number of other players' answers ( $= N$ )	1
the next three rows repeat $N$ times
player ID	1
answer data size ( $= L_i$ )	1
answer data	$L_i$

Table 5: synchronization packet for problem-end

Content	Size
packet header	3
result	1

A type A packet is therefore $4 + N$ bytes long, and a type B packet is $4 + \sum_{i=1}^{N} (2 + L_i)$ bytes long.

Input

The input holds several test cases. Each test case begins with a line holding two integers $M$ and $N$ ( $1 \le M, N \le 100$ ), the number of players and the number of problems. The next line holds $M$ non-negative integers $D_0, D_1, \ldots, D_{M-1}$ ( $0 \le D_i \le 10^4$ ), the one-way delay in milliseconds between each player and the server. Player IDs run from $0$ to $M-1$ .

Then come $N$ blocks, one per problem, in the order the problems are presented. A block begins with a line holding an integer $L$ ( $0 \le L \le M$ ), the number of players that submitted an answer for that problem, and continues with $L$ lines. Each of those lines holds three fields $P$ , $T$ and $A$ separated by whitespace. $P$ is a player ID, $T$ is the time in milliseconds that passed on the player's side between receiving the synchronization packet for problem-start and submitting, and $A$ is that player's answer, an alphanumeric string whose length is between 1 and 9 inclusive. The $L$ lines of a block come in arbitrary order, and no player appears twice in the same block. Every answer packet reaches the server within 19,999 milliseconds after the synchronization packet for problem-start is sent, so $T + 2 \times D_P \le 19999$ holds.

The input ends with a line holding two zeros.

Output

For each test case print $M + 1$ lines. On the first line print how many bytes the server sent and how many bytes the server received, separated by a space. On each of the next $M$ lines print how many bytes one player sent and how many bytes that player received, separated by a space, in increasing order of player ID. Print a blank line between two consecutive test cases.

Examples2

Example 1

Input

3 2
1 2 10
3
0 3420 o
1 4589 o
2 4638 x
3
1 6577 SUZUMIYA
2 7644 SUZUMIYA
0 19979 YASUZUMI
4 2
150 150 150 150
4
0 1344 HOGEHOGE
1 1466 HOGEHOGE
2 1789 HOGEHOGE
3 19100 GEHO
2
2 1200 SETTEN
3 700 SETTEN
0 0

Expected output

Example 2
Input
```
1 1
0
1
0 500 A
0 0
```
Expected output
```
7 6
6 7
```