No tags yet

No tag edit access

The problem statement has recently been changed. View the changes.

×
time limit per test: 0.25 sec.

memory limit per test: 65536 KB

memory limit per test: 65536 KB

input: standard

output: standard

output: standard

The new secret counter invented in one theoretical computer science lab is the great breakthrough in the computer microschemes design. This counter consists of N registers numbered from 0 to N-1, each of which contains 0, 1 or 2. If the number in the i-th register is A_{i}, the number stored in the counter is

A_{N-1} * 2^{N-1} + A_{N-2} * 2^{N-2} + ... + A_{1} * 2 + A_{0}

One can see that the same number can be stored in the counter in several different ways. For example, the number 5 can be stored in a 3-register counter as (1, 0, 1) or as (0, 2, 1).

The main feature of the counter is that it can add numbers that are powers of two to the number stored in the counter, only changing the value of a small number of registers. Namely, the scientists of the lab developed the scheme that allowed adding such number changing no more than four registers!

Unfortunately after the recent experiments in the neighbouring physics lab, involving the creation of the artificial black hole, the theoretical computer science laboratory was accidently destroyed. However, the supercomputer project that the counter was designed for is still on, so you were asked to reinvent the counter.

A

One can see that the same number can be stored in the counter in several different ways. For example, the number 5 can be stored in a 3-register counter as (1, 0, 1) or as (0, 2, 1).

The main feature of the counter is that it can add numbers that are powers of two to the number stored in the counter, only changing the value of a small number of registers. Namely, the scientists of the lab developed the scheme that allowed adding such number changing no more than four registers!

Unfortunately after the recent experiments in the neighbouring physics lab, involving the creation of the artificial black hole, the theoretical computer science laboratory was accidently destroyed. However, the supercomputer project that the counter was designed for is still on, so you were asked to reinvent the counter.

The first line of the input file contains N — the number of registers in the counter (1 ≤ N ≤ 1 000). Initially all registers contain zeroes. The second line contains M — the number of additions you have to make (1 ≤ M ≤ 10 000). The third line contains M integer numbers ranging from 0 to N-1. Number i means that you must add 2

Output file must contain M lines. Each line must contain the changes made adding the corresponding number to the counter.

The first number in each line must be K — the number of registers changed (1 ≤ K ≤ 4). K pairs must follow — for each changed register first output its number and then the new value.

Input

5

6

0 0 0 1 0 0

6

0 0 0 1 0 0

Output

1 0 1

1 0 2

2 0 1 1 1

1 1 2

1 0 2

3 0 1 1 1 2 1

1 0 2

2 0 1 1 1

1 1 2

1 0 2

3 0 1 1 1 2 1

Author: | Andrew Stankevich |

Resource: | Petrozavodsk Summer Trainings 2003 |

Date: | 2003-08-30 |

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/04/2021 10:49:56 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|