Paragraph Formatting

All submissions for this problem are available.

Johnny is developing some word processing software. Right now, he has to deal with the problem of formatting a paragraph. Johnny has formulated the problem as follows.

There are N words in a paragraph, in which the i^th word has a_i characters. Each line of the paragraph can hold at most M characters. For simplicity, we assume that every two consecutive words in a line are separated by exactly one whitespace and we disregard punctuation marks.

The text editor always uses a simple greedy algorithm to break the paragraph into lines. The algorithm puts as many words in a line as possible, then moving on to the next line to do the same until there are no more words left to be placed.

Johnny needs to write a program that, given the description of the words in a paragraph, is able to process the following two operations:

• Return the line number of a specified word
• Replace one word with another one

Since the number of words in a paragraph can be huge, Johnny needs to find an efficient algorithm to process the above queries. Please help him!

Input

The first line contains t, the number of test cases (about 50). Then t test cases follow. Each test case has the following form:

• The first line contains a number M, the maximum number of characters that can be put in a line.
• The second line contains a number N, the number of words in the given paragraph.
• The third line contains N numbers a₁, a₂, ..., a_N, the lengths of the words in the paragraph.
• The next lines contain the description of the queries, one query in a line. Each query can be of one of the following 3 types:
• I i - Ask for the line number of the i^th word.
• C i l - Replace the i^th word by a new word of length l (1 ≤ l ≤ M).
• E - Signal the end of the description of the queries.

Note that the line numbers and the word indexes are counted from 1.

Output

For each test case, the first line of output should contain the string "Case #T:" where T should be replaced by the corresponding test case number.

For every 'I' query in the test case, print the correct line number of the word being queried.

Print a blank line after each test case.

Constraints

• 1 ≤ N ≤ 50000
• 1 ≤ M ≤ 100000
• 1 ≤ a_i ≤ M
• The number of lines in each paragraph never exceeds 200.
• The number of queries in each test case does not exceed 10000.

Example

Input:
2

4
2
1 2
I 2
C 2 3
I 2
E

6
5
1 5 4 5 6
I 2
I 4
I 5
C 4 1
I 4
I 5
C 2 1
C 3 2
C 5 4
I 5
I 3
E

Output:
Case #1:
1
2

Case #2:
2
4
5
3
4
2
1

Discussion of the example

In the following description of the second exemplary test case, we use the digit i to denote a character of the i^th word. Note that each line can hold at most 6 characters. Initially, the paragraph has the following form:

1
22222
3333
44444
555555

After replacing the 4^thword with a one-character word, the paragraph becomes:

1
22222
3333 4
555555

After the last 3 replacements, the paragraph becomes:

1 2 33
4 5555

---

Date:	2009-09-15
Time limit:	3.5s
Source limit:	50000B
Languages:	All except: PERL6 ERL JS