---
{"languages_supported":{"0":"NA"},"title":"H5","category":"NA","old_version":true,"problem_code":"H5","tags":{"0":"NA"},"layout":"problem"}
---
<h3> All submissions for this problem are available. </h3><p>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.</p>
<p>There are N words in a paragraph, in which the i<sup>th</sup> word has a<sub>i</sub> 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 <b>exactly one whitespace</b> and we disregard punctuation marks.</p>
<p>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.</p>
<p>Johnny needs to write a program that, given the description of the words in a paragraph, is able to process the following two operations:</p>
<ul>
<li>Return the line number of a specified word</li>
<li>Replace one word with another one</li>
</ul>
<p>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!</p>
<h3>Input</h3>
<p>The first line contains t, the number of test cases (about 50). Then t test cases follow. Each test case has the following form:</p>
<ul>
<li>The first line contains a number M, the maximum number of characters that can be put in a line.</li>
<li>The second line contains a number N, the number of words in the given paragraph.</li>
<li>The third line contains N numbers a<sub>1</sub>, a<sub>2</sub>, ..., a<sub>N</sub>, the lengths of the words in the paragraph.</li>
<li>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:
<ul>
<li><i>I i</i> - Ask for the line number of the i<sup>th</sup> word.</li>
<li><i>C i l</i> - Replace the i<sup>th</sup> word by a new word of length l (1 ≤ l ≤ M).</li>
<li><i>E</i> - Signal the end of the description of the queries.</li>
</ul>
</li>
</ul>
<p>Note that the line numbers and the word indexes are counted from 1.</p>
<p> </p>
<p>The input data for successive test cases is separated by a blank line.</p>
<h3>Output</h3>
<p>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.</p>
<p>For every 'I' query in the test case, print the correct line number of the word being queried.</p>
<p>Print a blank line after each test case.</p>
<h3>Constraints</h3>
<ul>
<li>1 ≤ N ≤ 50000</li>
<li>1 ≤ M ≤ 100000</li>
<li>1 ≤ a<sub>i</sub> ≤ M</li>
<li>The number of lines in each paragraph never exceeds 200.</li>
<li>The number of queries in each test case does not exceed 10000.</li>
</ul>
<h3>Example</h3>
<pre><b>Input:</b><br />2<br /><br />4<br />2<br />1 2<br />I 2<br />C 2 3<br />I 2<br />E<br /><br />6<br />5<br />1 5 4 5 6<br />I 2<br />I 4<br />I 5<br />C 4 1<br />I 4<br />I 5<br />C 2 1<br />C 3 2<br />C 5 4<br />I 5<br />I 3<br />E<br /><br /><b>Output:</b><br />Case #1:<br />1<br />2<br /><br />Case #2:<br />2<br />4<br />5<br />3<br />4<br />2<br />1<br /></pre>
<h3>Discussion of the example</h3>
<p>In the following description of the second exemplary test case, we use the digit i to denote a character of the i<sup>th</sup> word. Note that each line can hold at most 6 characters. Initially, the paragraph has the following form:</p>
<pre>1<br />22222<br />3333<br />44444<br />555555<br /></pre>
<p>After replacing the 4<sup>th</sup>word with a one-character word, the paragraph becomes:</p>
<pre>1<br />22222<br />3333 4<br />555555<br /></pre>
<p>After the last 3 replacements, the paragraph becomes:</p>
<pre>1 2 33<br />4 5555<br /></pre>
<p></p>