作者： chenchen

**Note: The time limit for this problem is 4s, 2x the default.**

To celebrate the start of spring, Farmer John's N cows (1≤N≤2⋅10⁵ ) have invented an intriguing new dance, where they stand in a circle and re-order themselves in a predictable way.

Specifically, there are N positions around the circle, numbered sequentially from 0 to N−1, with position 0 following position N−1. A cow resides at each position. The cows are also numbered sequentially from 0 to N−1. Initially, cow i starts in position i. You are told a set of K positions 0=A₁<A₂<…<A_K<N that are "active", meaning the cows in these positions are the next to move (1≤K≤N).

In each minute of the dance, two things happen. First, the cows in the active positions rotate: the cow at position A₁ moves to position A₂, the cow at position A₂ moves to position A₃, and so on, with the cow at position AK moving to position A₁. All of these K moves happen simultaneously, so the after the rotation is complete, all of the active positions still contain exactly one cow. Next, the active positions themselves shift: A₁ becomes A₁+1,A₂ becomes A₂+1, and so on (if A_i =N−1 for some active position, then Ai circles back around to 0).

Please calculate the order of the cows after T minutes of the dance (1≤T≤109).

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains three integers N, K, and T.
The second line contains K integers representing the initial set of active positionsA₁,A₂,…A_K. Recall that A₁=0 and that these are given in increasing order.

OUTPUT FORMAT (print output to the terminal / stdout):

Output the order of the cows after T minutes, starting with the cow in position 0, separated by spaces.

SAMPLE INPUT:

5 3 4
0 2 3

SAMPLE OUTPUT:

1 2 3 4 0
For the example above, here are the cow orders and A
for the first four timesteps:

Initial, T = 0: order = [0 1 2 3 4], A = [0 2 3]
T = 1: order = [3 1 0 2 4]
T = 1: A = [1 3 4]
T = 2: order = [3 4 0 1 2]
T = 2: A = [2 4 0]
T = 3: order = [2 4 3 1 0]
T = 3: A = [3 0 1]
T = 4: order = [1 2 3 4 0]

SCORING:

Inputs 2-7: N≤1000,T≤10000
Inputs 8-13: No additional constraints.
Problem credits: Claire Zhang

Farmer John is interested in better interacting with his fellow cows, so he decided he will learn the moo language!

Moo language is actually quite similar to English, but more minimalistic. There are only four types of words: nouns, transitive verbs, intransitive verbs, and conjunctions. Every two consecutive words must be separated by a space. There are also only two types of punctuation: periods and commas. When a period or comma appears after a word, it appears directly after the word, and is then followed by a space if another word appears next.

A sentence needs to follow one of the following formats:

Type 1: noun + intransitive verb.
Type 2: noun + transitive verb + noun(s). Specifically, at least one noun must follow the transitive verb, and there must be a comma in front of every following noun besides the first following noun.
Two sentences may be joined into a compound sentence if a conjunction is placed in between them. The resulting compound sentence cannot be further joined with other sentences or other compound sentences. Every sentence (or compound sentence, if two sentences are joined) must end with a period.

Farmer John has a word bank of N words, C commas, and P periods (1≤P,C≤N≤10³). He may only use a word or punctuation mark as many times as it appears in the word bank. Help him output a sequence of sentences containing the maximum possible number of words.

Each input file contains T (1≤T≤100) independent instances of this problem.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains T, the number of instances. Each instance is specified as follows:The first line consists of three integers, N, C, and P.

The N following lines will consist of two strings. The first string will be the word itself that FJ can use (a string of at least 1 and at most 10 lowercase letters), and the second string will be either one of the following: noun, transitive-verb, intransitive-verb, or conjunction, denoting the type of the word. It is possible the same word occurs more than once in FJ's word bank, but it will always have the same type each time it appears.

OUTPUT FORMAT (print output to the terminal / stdout):

In the first line, output the maximum possible number of words.
In the second line, output any sequence of sentences with the maximum possible number of words. Any valid sequence will be accepted.

The grader is sensitive to whitespace, so make sure not to output any extraneous spaces, particularly at the end of each line.

SAMPLE INPUT:

3
1 1 1
bessie noun
10 5 4
bessie noun
taught transitive-verb
flew intransitive-verb
elsie noun
farmer noun
john noun
and conjunction
and conjunction
nhoj noun
mooed intransitive-verb
24 5 4
but conjunction
bessie noun
taught transitive-verb
flew intransitive-verb
elsie noun
farmer noun
john noun
and conjunction
and conjunction
nhoj noun
mooed intransitive-verb
bob noun
impressed transitive-verb
cow noun
impressed transitive-verb
leaped intransitive-verb
elsie noun
bella noun
buttercup noun
pushed transitive-verb
mooed intransitive-verb
envy noun
john noun
nhoj noun

SAMPLE OUTPUT:

0

9
nhoj mooed. farmer taught elsie, bessie and john flew.
23
nhoj mooed. nhoj impressed john, farmer, elsie, bessie and cow impressed bob. bella pushed elsie and buttercup flew. envy mooed but john leaped.
For the first test case, the only valid sequence is the empty sequence. For each of the next two test cases, it is possible to construct a sequence of sentences using every word from the word bank except for one.

SCORING:

Inputs 2-6: N≤10
Inputs 7-11: N≤100
Inputs 12-16: N≤1000
Inputs with remainder 2 when divided by 5: There are no transitive verbs.
Inputs with remainder 3 when divided by 5: There are no intransitive verbs.
Inputs with remainder 4 when divided by 5: There are no conjunctions.

Problem credits: Chongtian Ma

Bessie and Elsie are plotting to overthrow Farmer John at last! They plan it out over N (1≤N≤2⋅10⁵) text messages. Their conversation can be represented by a string S of length N where S_i is either B or E, meaning the ith message was sent by Bessie or Elsie, respectively.

However, Farmer John hears of the plan and attempts to intercept their conversation. Thus, some letters of S are F, meaning Farmer John obfuscated the message and the sender is unknown.

The excitement level of a non-obfuscated conversation is the number of times a cow double-sends - that is, the number of occurrences of substring BBor EE in S. You want to find the excitement level of the original message, but you don’t know which of Farmer John’s messages were actually Bessie’s / Elsie’s. Over all possibilities, output all possible excitement levels of S.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line will consist of one integer N.
The next line contains S.

OUTPUT FORMAT (print output to the terminal / stdout):

First output K, the number of distinct excitement levels possible. On the next K
lines, output the excitement levels, in increasing order.

SAMPLE INPUT:

4
BEEF

SAMPLE OUTPUT:

2
1
2

SAMPLE INPUT:

9
FEBFEBFEB

SAMPLE OUTPUT:
2
2
3

SAMPLE INPUT:
10
BFFFFFEBFE

SAMPLE OUTPUT:
3
2
4
6

SCORING:
Inputs 4-8: N≤10
Inputs 9-20: No additional constraints.
Problem credits: William Yue and Claire Zhang