Filtration

Digital signal processing (DSP) creates effects such as the "echo" often heard in music, or the modulation applied to certain singers' voices. These effects are produced with Finite Impulse Response (FIR) filters.

Consider an input stream of samples: a sequence of integers, each between 0 and 255 inclusive (the range of an 8-bit sample). The samples arrive one after another as the digital representation of a waveform. An FIR mixer combines several streams into one; an FIR echo filter turns one input into one output; and so on.

An FIR filter is written as an equation, with the input signals on one side and the output on the other. For example,

Y = X[0] + X[-5]

is a (post-)echo filter: sample $i$ of $Y$ equals the value of $X$ at the same position plus the value of $X$ five samples earlier. In general, a reference $X[k]$ used while producing output position $i$ reads $X[i + k]$; if $i + k$ falls outside the valid range $0 \dots S-1$, that value is taken to be 0.

Every FIR equation obeys the following Backus-Naur Form (BNF) grammar:

EQUATION ::= STREAM __ "=" __ EXPR
STREAM   ::= a single upper-case letter naming a sample stream, such as A or X
EXPR     ::= VALUE | SAMPLE | EXPR __ OPER __ EXPR | "(" __ EXPR __ ")"
VALUE    ::= a floating-point number, such as 0.25, 5, or -1.5
SAMPLE   ::= STREAM "[" OFFSET "]"
OFFSET   ::= an integer sample offset, such as 0, 1, or -5, between -100 and 100 inclusive
OPER     ::= "*" | "+" | "-"

Operators follow the usual precedence (parentheses first, then multiplication, then addition and subtraction, otherwise left to right). Only after all of a filter's arithmetic is complete is the result rounded down (floored) to the nearest integer and then clamped to the range $0 \dots 255$; this clamped 8-bit value is the filter's output sample. The __ symbol denotes one or more spaces, and whitespace is allowed only where the grammar explicitly shows it.

For example, a simple low-pass filter can be written as

Z = 0.5 * Y[0] + 0.25 * Y[-1] + 0.25 * Y[1]

Each output of $Z$ is based on the matching value of $Y$, adjusted by its nearest neighbours. A simple mixer can be written as

D = C[0] + B[0]

though such a filter can obviously clip.

For more complex effects, filters are chained together. Here every stream is either an input stream (for example, the source audio) or the output of a single FIR filter. A stream may be used as an input by more than one filter, forming a filter network.

Given a set of FIR filter definitions and starting inputs, output all of the filter outputs. No FIR filter uses more than 10 operators, more than ten pairs of parentheses, or more than 80 characters. Each data set has at least one input stream and at least one filter, and every stream referenced by a filter is defined in the same data set. All streams in a data set have the same number of samples, and the network has no feedback loops — no filter depends, directly or indirectly, on its own output.

(Although feedback loops sure sound cool when Pete Townshend uses them.)

The first line contains a single integer $D$ ($1 \le D \le 100$), the number of data sets. Each data set consists of:

• A line with a single integer $N$ ($2 \le N \le 26$), the number of streams in the data set.
• A line with a single integer $S$ ($1 \le S \le 100$), the number of samples in every stream.
• $N$ lines, each describing one stream. Stream names are distinct within a data set. Each line is one of:
  • an input stream, written STREAM % sam1 sam2 sam3 … samS, where STREAM is a single capital letter and sam1 … samS are its samples. The samples and the % marker are separated by whitespace.
  • an FIR filter, written STREAM = EXPR as described above.

For each data set, print a header line DATA SET #k, where $k$ is 1 for the first data set, 2 for the second, and so on. Then, for every FIR filter in that data set (in alphabetical order by stream name), print its output stream on its own line in the form STREAM % sam1 sam2 sam3 … samS. Input streams are not printed.