github.com/captn3m0/codechef.git

---
languages_supported:
    - NA
title: H5
category: NA
old_version: true
problem_code: H5
tags:
    - NA
layout: problem
---
###  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 ith word has ai 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 a1, a2, ..., aN, 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 ith word.
  - _C i l_ - Replace the ith 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.

The input data for successive test cases is separated by a blank line.

### 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 ≤ ai ≤ M
- The number of lines in each paragraph never exceeds 200.
- The number of queries in each test case does not exceed 10000.

### Example

`<b>Input:</b><br></br>2<br></br><br></br>4<br></br>2<br></br>1 2<br></br>I 2<br></br>C 2 3<br></br>I 2<br></br>E<br></br><br></br>6<br></br>5<br></br>1 5 4 5 6<br></br>I 2<br></br>I 4<br></br>I 5<br></br>C 4 1<br></br>I 4<br></br>I 5<br></br>C 2 1<br></br>C 3 2<br></br>C 5 4<br></br>I 5<br></br>I 3<br></br>E<br></br><br></br><b>Output:</b><br></br>Case #1:<br></br>1<br></br>2<br></br><br></br>Case #2:<br></br>2<br></br>4<br></br>5<br></br>3<br></br>4<br></br>2<br></br>1<br></br>`### 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 ith word. Note that each line can hold at most 6 characters. Initially, the paragraph has the following form:

`1<br></br>22222<br></br>3333<br></br>44444<br></br>555555<br></br>`After replacing the 4thword with a one-character word, the paragraph becomes:

`1<br></br>22222<br></br>3333 4<br></br>555555<br></br>`After the last 3 replacements, the paragraph becomes:

`1 2 33<br></br>4 5555<br></br>`