1//===----------------------------------------------------------------------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is dual licensed under the MIT and the University of Illinois Open
6// Source Licenses. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9
10// <string>
11
12// basic_string<charT,traits,Allocator>&
13//   insert(size_type pos1, const basic_string<charT,traits,Allocator>& str,
14//          size_type pos2, size_type n=npos);
15// the "=npos" was added in C++14
16
17#include <string>
18#include <stdexcept>
19#include <cassert>
20
21#include "min_allocator.h"
22
23template <class S>
24void
25test(S s, typename S::size_type pos1, S str, typename S::size_type pos2,
26     typename S::size_type n, S expected)
27{
28    typename S::size_type old_size = s.size();
29    S s0 = s;
30    try
31    {
32        s.insert(pos1, str, pos2, n);
33        assert(s.__invariants());
34        assert(pos1 <= old_size && pos2 <= str.size());
35        assert(s == expected);
36    }
37    catch (std::out_of_range&)
38    {
39        assert(pos1 > old_size || pos2 > str.size());
40        assert(s == s0);
41    }
42}
43
44template <class S>
45void
46test_npos(S s, typename S::size_type pos1, S str, typename S::size_type pos2, S expected)
47{
48    typename S::size_type old_size = s.size();
49    S s0 = s;
50    try
51    {
52        s.insert(pos1, str, pos2);
53        assert(s.__invariants());
54        assert(pos1 <= old_size && pos2 <= str.size());
55        assert(s == expected);
56    }
57    catch (std::out_of_range&)
58    {
59        assert(pos1 > old_size || pos2 > str.size());
60        assert(s == s0);
61    }
62}
63
64
65template <class S>
66void test0()
67{
68    test(S(""), 0, S(""), 0, 0, S(""));
69    test(S(""), 0, S(""), 0, 1, S(""));
70    test(S(""), 0, S(""), 1, 0, S("can't happen"));
71    test(S(""), 0, S("12345"), 0, 0, S(""));
72    test(S(""), 0, S("12345"), 0, 1, S("1"));
73    test(S(""), 0, S("12345"), 0, 2, S("12"));
74    test(S(""), 0, S("12345"), 0, 4, S("1234"));
75    test(S(""), 0, S("12345"), 0, 5, S("12345"));
76    test(S(""), 0, S("12345"), 0, 6, S("12345"));
77    test(S(""), 0, S("12345"), 1, 0, S(""));
78    test(S(""), 0, S("12345"), 1, 1, S("2"));
79    test(S(""), 0, S("12345"), 1, 2, S("23"));
80    test(S(""), 0, S("12345"), 1, 3, S("234"));
81    test(S(""), 0, S("12345"), 1, 4, S("2345"));
82    test(S(""), 0, S("12345"), 1, 5, S("2345"));
83    test(S(""), 0, S("12345"), 2, 0, S(""));
84    test(S(""), 0, S("12345"), 2, 1, S("3"));
85    test(S(""), 0, S("12345"), 2, 2, S("34"));
86    test(S(""), 0, S("12345"), 2, 3, S("345"));
87    test(S(""), 0, S("12345"), 2, 4, S("345"));
88    test(S(""), 0, S("12345"), 4, 0, S(""));
89    test(S(""), 0, S("12345"), 4, 1, S("5"));
90    test(S(""), 0, S("12345"), 4, 2, S("5"));
91    test(S(""), 0, S("12345"), 5, 0, S(""));
92    test(S(""), 0, S("12345"), 5, 1, S(""));
93    test(S(""), 0, S("12345"), 6, 0, S("can't happen"));
94    test(S(""), 0, S("1234567890"), 0, 0, S(""));
95    test(S(""), 0, S("1234567890"), 0, 1, S("1"));
96    test(S(""), 0, S("1234567890"), 0, 5, S("12345"));
97    test(S(""), 0, S("1234567890"), 0, 9, S("123456789"));
98    test(S(""), 0, S("1234567890"), 0, 10, S("1234567890"));
99    test(S(""), 0, S("1234567890"), 0, 11, S("1234567890"));
100    test(S(""), 0, S("1234567890"), 1, 0, S(""));
101    test(S(""), 0, S("1234567890"), 1, 1, S("2"));
102    test(S(""), 0, S("1234567890"), 1, 4, S("2345"));
103    test(S(""), 0, S("1234567890"), 1, 8, S("23456789"));
104    test(S(""), 0, S("1234567890"), 1, 9, S("234567890"));
105    test(S(""), 0, S("1234567890"), 1, 10, S("234567890"));
106    test(S(""), 0, S("1234567890"), 5, 0, S(""));
107    test(S(""), 0, S("1234567890"), 5, 1, S("6"));
108    test(S(""), 0, S("1234567890"), 5, 2, S("67"));
109    test(S(""), 0, S("1234567890"), 5, 4, S("6789"));
110    test(S(""), 0, S("1234567890"), 5, 5, S("67890"));
111    test(S(""), 0, S("1234567890"), 5, 6, S("67890"));
112    test(S(""), 0, S("1234567890"), 9, 0, S(""));
113    test(S(""), 0, S("1234567890"), 9, 1, S("0"));
114    test(S(""), 0, S("1234567890"), 9, 2, S("0"));
115    test(S(""), 0, S("1234567890"), 10, 0, S(""));
116    test(S(""), 0, S("1234567890"), 10, 1, S(""));
117    test(S(""), 0, S("1234567890"), 11, 0, S("can't happen"));
118}
119
120template <class S>
121void test1()
122{
123    test(S(""), 0, S("12345678901234567890"), 0, 0, S(""));
124    test(S(""), 0, S("12345678901234567890"), 0, 1, S("1"));
125    test(S(""), 0, S("12345678901234567890"), 0, 10, S("1234567890"));
126    test(S(""), 0, S("12345678901234567890"), 0, 19, S("1234567890123456789"));
127    test(S(""), 0, S("12345678901234567890"), 0, 20, S("12345678901234567890"));
128    test(S(""), 0, S("12345678901234567890"), 0, 21, S("12345678901234567890"));
129    test(S(""), 0, S("12345678901234567890"), 1, 0, S(""));
130    test(S(""), 0, S("12345678901234567890"), 1, 1, S("2"));
131    test(S(""), 0, S("12345678901234567890"), 1, 9, S("234567890"));
132    test(S(""), 0, S("12345678901234567890"), 1, 18, S("234567890123456789"));
133    test(S(""), 0, S("12345678901234567890"), 1, 19, S("2345678901234567890"));
134    test(S(""), 0, S("12345678901234567890"), 1, 20, S("2345678901234567890"));
135    test(S(""), 0, S("12345678901234567890"), 10, 0, S(""));
136    test(S(""), 0, S("12345678901234567890"), 10, 1, S("1"));
137    test(S(""), 0, S("12345678901234567890"), 10, 5, S("12345"));
138    test(S(""), 0, S("12345678901234567890"), 10, 9, S("123456789"));
139    test(S(""), 0, S("12345678901234567890"), 10, 10, S("1234567890"));
140    test(S(""), 0, S("12345678901234567890"), 10, 11, S("1234567890"));
141    test(S(""), 0, S("12345678901234567890"), 19, 0, S(""));
142    test(S(""), 0, S("12345678901234567890"), 19, 1, S("0"));
143    test(S(""), 0, S("12345678901234567890"), 19, 2, S("0"));
144    test(S(""), 0, S("12345678901234567890"), 20, 0, S(""));
145    test(S(""), 0, S("12345678901234567890"), 20, 1, S(""));
146    test(S(""), 0, S("12345678901234567890"), 21, 0, S("can't happen"));
147    test(S(""), 1, S(""), 0, 0, S("can't happen"));
148    test(S(""), 1, S(""), 0, 1, S("can't happen"));
149    test(S(""), 1, S(""), 1, 0, S("can't happen"));
150    test(S(""), 1, S("12345"), 0, 0, S("can't happen"));
151    test(S(""), 1, S("12345"), 0, 1, S("can't happen"));
152    test(S(""), 1, S("12345"), 0, 2, S("can't happen"));
153    test(S(""), 1, S("12345"), 0, 4, S("can't happen"));
154    test(S(""), 1, S("12345"), 0, 5, S("can't happen"));
155    test(S(""), 1, S("12345"), 0, 6, S("can't happen"));
156    test(S(""), 1, S("12345"), 1, 0, S("can't happen"));
157    test(S(""), 1, S("12345"), 1, 1, S("can't happen"));
158    test(S(""), 1, S("12345"), 1, 2, S("can't happen"));
159    test(S(""), 1, S("12345"), 1, 3, S("can't happen"));
160    test(S(""), 1, S("12345"), 1, 4, S("can't happen"));
161    test(S(""), 1, S("12345"), 1, 5, S("can't happen"));
162    test(S(""), 1, S("12345"), 2, 0, S("can't happen"));
163    test(S(""), 1, S("12345"), 2, 1, S("can't happen"));
164    test(S(""), 1, S("12345"), 2, 2, S("can't happen"));
165    test(S(""), 1, S("12345"), 2, 3, S("can't happen"));
166    test(S(""), 1, S("12345"), 2, 4, S("can't happen"));
167    test(S(""), 1, S("12345"), 4, 0, S("can't happen"));
168    test(S(""), 1, S("12345"), 4, 1, S("can't happen"));
169    test(S(""), 1, S("12345"), 4, 2, S("can't happen"));
170    test(S(""), 1, S("12345"), 5, 0, S("can't happen"));
171    test(S(""), 1, S("12345"), 5, 1, S("can't happen"));
172    test(S(""), 1, S("12345"), 6, 0, S("can't happen"));
173}
174
175template <class S>
176void test2()
177{
178    test(S(""), 1, S("1234567890"), 0, 0, S("can't happen"));
179    test(S(""), 1, S("1234567890"), 0, 1, S("can't happen"));
180    test(S(""), 1, S("1234567890"), 0, 5, S("can't happen"));
181    test(S(""), 1, S("1234567890"), 0, 9, S("can't happen"));
182    test(S(""), 1, S("1234567890"), 0, 10, S("can't happen"));
183    test(S(""), 1, S("1234567890"), 0, 11, S("can't happen"));
184    test(S(""), 1, S("1234567890"), 1, 0, S("can't happen"));
185    test(S(""), 1, S("1234567890"), 1, 1, S("can't happen"));
186    test(S(""), 1, S("1234567890"), 1, 4, S("can't happen"));
187    test(S(""), 1, S("1234567890"), 1, 8, S("can't happen"));
188    test(S(""), 1, S("1234567890"), 1, 9, S("can't happen"));
189    test(S(""), 1, S("1234567890"), 1, 10, S("can't happen"));
190    test(S(""), 1, S("1234567890"), 5, 0, S("can't happen"));
191    test(S(""), 1, S("1234567890"), 5, 1, S("can't happen"));
192    test(S(""), 1, S("1234567890"), 5, 2, S("can't happen"));
193    test(S(""), 1, S("1234567890"), 5, 4, S("can't happen"));
194    test(S(""), 1, S("1234567890"), 5, 5, S("can't happen"));
195    test(S(""), 1, S("1234567890"), 5, 6, S("can't happen"));
196    test(S(""), 1, S("1234567890"), 9, 0, S("can't happen"));
197    test(S(""), 1, S("1234567890"), 9, 1, S("can't happen"));
198    test(S(""), 1, S("1234567890"), 9, 2, S("can't happen"));
199    test(S(""), 1, S("1234567890"), 10, 0, S("can't happen"));
200    test(S(""), 1, S("1234567890"), 10, 1, S("can't happen"));
201    test(S(""), 1, S("1234567890"), 11, 0, S("can't happen"));
202    test(S(""), 1, S("12345678901234567890"), 0, 0, S("can't happen"));
203    test(S(""), 1, S("12345678901234567890"), 0, 1, S("can't happen"));
204    test(S(""), 1, S("12345678901234567890"), 0, 10, S("can't happen"));
205    test(S(""), 1, S("12345678901234567890"), 0, 19, S("can't happen"));
206    test(S(""), 1, S("12345678901234567890"), 0, 20, S("can't happen"));
207    test(S(""), 1, S("12345678901234567890"), 0, 21, S("can't happen"));
208    test(S(""), 1, S("12345678901234567890"), 1, 0, S("can't happen"));
209    test(S(""), 1, S("12345678901234567890"), 1, 1, S("can't happen"));
210    test(S(""), 1, S("12345678901234567890"), 1, 9, S("can't happen"));
211    test(S(""), 1, S("12345678901234567890"), 1, 18, S("can't happen"));
212    test(S(""), 1, S("12345678901234567890"), 1, 19, S("can't happen"));
213    test(S(""), 1, S("12345678901234567890"), 1, 20, S("can't happen"));
214    test(S(""), 1, S("12345678901234567890"), 10, 0, S("can't happen"));
215    test(S(""), 1, S("12345678901234567890"), 10, 1, S("can't happen"));
216    test(S(""), 1, S("12345678901234567890"), 10, 5, S("can't happen"));
217    test(S(""), 1, S("12345678901234567890"), 10, 9, S("can't happen"));
218    test(S(""), 1, S("12345678901234567890"), 10, 10, S("can't happen"));
219    test(S(""), 1, S("12345678901234567890"), 10, 11, S("can't happen"));
220    test(S(""), 1, S("12345678901234567890"), 19, 0, S("can't happen"));
221    test(S(""), 1, S("12345678901234567890"), 19, 1, S("can't happen"));
222    test(S(""), 1, S("12345678901234567890"), 19, 2, S("can't happen"));
223    test(S(""), 1, S("12345678901234567890"), 20, 0, S("can't happen"));
224    test(S(""), 1, S("12345678901234567890"), 20, 1, S("can't happen"));
225    test(S(""), 1, S("12345678901234567890"), 21, 0, S("can't happen"));
226    test(S("abcde"), 0, S(""), 0, 0, S("abcde"));
227    test(S("abcde"), 0, S(""), 0, 1, S("abcde"));
228}
229
230template <class S>
231void test3()
232{
233    test(S("abcde"), 0, S(""), 1, 0, S("can't happen"));
234    test(S("abcde"), 0, S("12345"), 0, 0, S("abcde"));
235    test(S("abcde"), 0, S("12345"), 0, 1, S("1abcde"));
236    test(S("abcde"), 0, S("12345"), 0, 2, S("12abcde"));
237    test(S("abcde"), 0, S("12345"), 0, 4, S("1234abcde"));
238    test(S("abcde"), 0, S("12345"), 0, 5, S("12345abcde"));
239    test(S("abcde"), 0, S("12345"), 0, 6, S("12345abcde"));
240    test(S("abcde"), 0, S("12345"), 1, 0, S("abcde"));
241    test(S("abcde"), 0, S("12345"), 1, 1, S("2abcde"));
242    test(S("abcde"), 0, S("12345"), 1, 2, S("23abcde"));
243    test(S("abcde"), 0, S("12345"), 1, 3, S("234abcde"));
244    test(S("abcde"), 0, S("12345"), 1, 4, S("2345abcde"));
245    test(S("abcde"), 0, S("12345"), 1, 5, S("2345abcde"));
246    test(S("abcde"), 0, S("12345"), 2, 0, S("abcde"));
247    test(S("abcde"), 0, S("12345"), 2, 1, S("3abcde"));
248    test(S("abcde"), 0, S("12345"), 2, 2, S("34abcde"));
249    test(S("abcde"), 0, S("12345"), 2, 3, S("345abcde"));
250    test(S("abcde"), 0, S("12345"), 2, 4, S("345abcde"));
251    test(S("abcde"), 0, S("12345"), 4, 0, S("abcde"));
252    test(S("abcde"), 0, S("12345"), 4, 1, S("5abcde"));
253    test(S("abcde"), 0, S("12345"), 4, 2, S("5abcde"));
254    test(S("abcde"), 0, S("12345"), 5, 0, S("abcde"));
255    test(S("abcde"), 0, S("12345"), 5, 1, S("abcde"));
256    test(S("abcde"), 0, S("12345"), 6, 0, S("can't happen"));
257    test(S("abcde"), 0, S("1234567890"), 0, 0, S("abcde"));
258    test(S("abcde"), 0, S("1234567890"), 0, 1, S("1abcde"));
259    test(S("abcde"), 0, S("1234567890"), 0, 5, S("12345abcde"));
260    test(S("abcde"), 0, S("1234567890"), 0, 9, S("123456789abcde"));
261    test(S("abcde"), 0, S("1234567890"), 0, 10, S("1234567890abcde"));
262    test(S("abcde"), 0, S("1234567890"), 0, 11, S("1234567890abcde"));
263    test(S("abcde"), 0, S("1234567890"), 1, 0, S("abcde"));
264    test(S("abcde"), 0, S("1234567890"), 1, 1, S("2abcde"));
265    test(S("abcde"), 0, S("1234567890"), 1, 4, S("2345abcde"));
266    test(S("abcde"), 0, S("1234567890"), 1, 8, S("23456789abcde"));
267    test(S("abcde"), 0, S("1234567890"), 1, 9, S("234567890abcde"));
268    test(S("abcde"), 0, S("1234567890"), 1, 10, S("234567890abcde"));
269    test(S("abcde"), 0, S("1234567890"), 5, 0, S("abcde"));
270    test(S("abcde"), 0, S("1234567890"), 5, 1, S("6abcde"));
271    test(S("abcde"), 0, S("1234567890"), 5, 2, S("67abcde"));
272    test(S("abcde"), 0, S("1234567890"), 5, 4, S("6789abcde"));
273    test(S("abcde"), 0, S("1234567890"), 5, 5, S("67890abcde"));
274    test(S("abcde"), 0, S("1234567890"), 5, 6, S("67890abcde"));
275    test(S("abcde"), 0, S("1234567890"), 9, 0, S("abcde"));
276    test(S("abcde"), 0, S("1234567890"), 9, 1, S("0abcde"));
277    test(S("abcde"), 0, S("1234567890"), 9, 2, S("0abcde"));
278    test(S("abcde"), 0, S("1234567890"), 10, 0, S("abcde"));
279    test(S("abcde"), 0, S("1234567890"), 10, 1, S("abcde"));
280    test(S("abcde"), 0, S("1234567890"), 11, 0, S("can't happen"));
281    test(S("abcde"), 0, S("12345678901234567890"), 0, 0, S("abcde"));
282    test(S("abcde"), 0, S("12345678901234567890"), 0, 1, S("1abcde"));
283}
284
285template <class S>
286void test4()
287{
288    test(S("abcde"), 0, S("12345678901234567890"), 0, 10, S("1234567890abcde"));
289    test(S("abcde"), 0, S("12345678901234567890"), 0, 19, S("1234567890123456789abcde"));
290    test(S("abcde"), 0, S("12345678901234567890"), 0, 20, S("12345678901234567890abcde"));
291    test(S("abcde"), 0, S("12345678901234567890"), 0, 21, S("12345678901234567890abcde"));
292    test(S("abcde"), 0, S("12345678901234567890"), 1, 0, S("abcde"));
293    test(S("abcde"), 0, S("12345678901234567890"), 1, 1, S("2abcde"));
294    test(S("abcde"), 0, S("12345678901234567890"), 1, 9, S("234567890abcde"));
295    test(S("abcde"), 0, S("12345678901234567890"), 1, 18, S("234567890123456789abcde"));
296    test(S("abcde"), 0, S("12345678901234567890"), 1, 19, S("2345678901234567890abcde"));
297    test(S("abcde"), 0, S("12345678901234567890"), 1, 20, S("2345678901234567890abcde"));
298    test(S("abcde"), 0, S("12345678901234567890"), 10, 0, S("abcde"));
299    test(S("abcde"), 0, S("12345678901234567890"), 10, 1, S("1abcde"));
300    test(S("abcde"), 0, S("12345678901234567890"), 10, 5, S("12345abcde"));
301    test(S("abcde"), 0, S("12345678901234567890"), 10, 9, S("123456789abcde"));
302    test(S("abcde"), 0, S("12345678901234567890"), 10, 10, S("1234567890abcde"));
303    test(S("abcde"), 0, S("12345678901234567890"), 10, 11, S("1234567890abcde"));
304    test(S("abcde"), 0, S("12345678901234567890"), 19, 0, S("abcde"));
305    test(S("abcde"), 0, S("12345678901234567890"), 19, 1, S("0abcde"));
306    test(S("abcde"), 0, S("12345678901234567890"), 19, 2, S("0abcde"));
307    test(S("abcde"), 0, S("12345678901234567890"), 20, 0, S("abcde"));
308    test(S("abcde"), 0, S("12345678901234567890"), 20, 1, S("abcde"));
309    test(S("abcde"), 0, S("12345678901234567890"), 21, 0, S("can't happen"));
310    test(S("abcde"), 1, S(""), 0, 0, S("abcde"));
311    test(S("abcde"), 1, S(""), 0, 1, S("abcde"));
312    test(S("abcde"), 1, S(""), 1, 0, S("can't happen"));
313    test(S("abcde"), 1, S("12345"), 0, 0, S("abcde"));
314    test(S("abcde"), 1, S("12345"), 0, 1, S("a1bcde"));
315    test(S("abcde"), 1, S("12345"), 0, 2, S("a12bcde"));
316    test(S("abcde"), 1, S("12345"), 0, 4, S("a1234bcde"));
317    test(S("abcde"), 1, S("12345"), 0, 5, S("a12345bcde"));
318    test(S("abcde"), 1, S("12345"), 0, 6, S("a12345bcde"));
319    test(S("abcde"), 1, S("12345"), 1, 0, S("abcde"));
320    test(S("abcde"), 1, S("12345"), 1, 1, S("a2bcde"));
321    test(S("abcde"), 1, S("12345"), 1, 2, S("a23bcde"));
322    test(S("abcde"), 1, S("12345"), 1, 3, S("a234bcde"));
323    test(S("abcde"), 1, S("12345"), 1, 4, S("a2345bcde"));
324    test(S("abcde"), 1, S("12345"), 1, 5, S("a2345bcde"));
325    test(S("abcde"), 1, S("12345"), 2, 0, S("abcde"));
326    test(S("abcde"), 1, S("12345"), 2, 1, S("a3bcde"));
327    test(S("abcde"), 1, S("12345"), 2, 2, S("a34bcde"));
328    test(S("abcde"), 1, S("12345"), 2, 3, S("a345bcde"));
329    test(S("abcde"), 1, S("12345"), 2, 4, S("a345bcde"));
330    test(S("abcde"), 1, S("12345"), 4, 0, S("abcde"));
331    test(S("abcde"), 1, S("12345"), 4, 1, S("a5bcde"));
332    test(S("abcde"), 1, S("12345"), 4, 2, S("a5bcde"));
333    test(S("abcde"), 1, S("12345"), 5, 0, S("abcde"));
334    test(S("abcde"), 1, S("12345"), 5, 1, S("abcde"));
335    test(S("abcde"), 1, S("12345"), 6, 0, S("can't happen"));
336    test(S("abcde"), 1, S("1234567890"), 0, 0, S("abcde"));
337    test(S("abcde"), 1, S("1234567890"), 0, 1, S("a1bcde"));
338}
339
340template <class S>
341void test5()
342{
343    test(S("abcde"), 1, S("1234567890"), 0, 5, S("a12345bcde"));
344    test(S("abcde"), 1, S("1234567890"), 0, 9, S("a123456789bcde"));
345    test(S("abcde"), 1, S("1234567890"), 0, 10, S("a1234567890bcde"));
346    test(S("abcde"), 1, S("1234567890"), 0, 11, S("a1234567890bcde"));
347    test(S("abcde"), 1, S("1234567890"), 1, 0, S("abcde"));
348    test(S("abcde"), 1, S("1234567890"), 1, 1, S("a2bcde"));
349    test(S("abcde"), 1, S("1234567890"), 1, 4, S("a2345bcde"));
350    test(S("abcde"), 1, S("1234567890"), 1, 8, S("a23456789bcde"));
351    test(S("abcde"), 1, S("1234567890"), 1, 9, S("a234567890bcde"));
352    test(S("abcde"), 1, S("1234567890"), 1, 10, S("a234567890bcde"));
353    test(S("abcde"), 1, S("1234567890"), 5, 0, S("abcde"));
354    test(S("abcde"), 1, S("1234567890"), 5, 1, S("a6bcde"));
355    test(S("abcde"), 1, S("1234567890"), 5, 2, S("a67bcde"));
356    test(S("abcde"), 1, S("1234567890"), 5, 4, S("a6789bcde"));
357    test(S("abcde"), 1, S("1234567890"), 5, 5, S("a67890bcde"));
358    test(S("abcde"), 1, S("1234567890"), 5, 6, S("a67890bcde"));
359    test(S("abcde"), 1, S("1234567890"), 9, 0, S("abcde"));
360    test(S("abcde"), 1, S("1234567890"), 9, 1, S("a0bcde"));
361    test(S("abcde"), 1, S("1234567890"), 9, 2, S("a0bcde"));
362    test(S("abcde"), 1, S("1234567890"), 10, 0, S("abcde"));
363    test(S("abcde"), 1, S("1234567890"), 10, 1, S("abcde"));
364    test(S("abcde"), 1, S("1234567890"), 11, 0, S("can't happen"));
365    test(S("abcde"), 1, S("12345678901234567890"), 0, 0, S("abcde"));
366    test(S("abcde"), 1, S("12345678901234567890"), 0, 1, S("a1bcde"));
367    test(S("abcde"), 1, S("12345678901234567890"), 0, 10, S("a1234567890bcde"));
368    test(S("abcde"), 1, S("12345678901234567890"), 0, 19, S("a1234567890123456789bcde"));
369    test(S("abcde"), 1, S("12345678901234567890"), 0, 20, S("a12345678901234567890bcde"));
370    test(S("abcde"), 1, S("12345678901234567890"), 0, 21, S("a12345678901234567890bcde"));
371    test(S("abcde"), 1, S("12345678901234567890"), 1, 0, S("abcde"));
372    test(S("abcde"), 1, S("12345678901234567890"), 1, 1, S("a2bcde"));
373    test(S("abcde"), 1, S("12345678901234567890"), 1, 9, S("a234567890bcde"));
374    test(S("abcde"), 1, S("12345678901234567890"), 1, 18, S("a234567890123456789bcde"));
375    test(S("abcde"), 1, S("12345678901234567890"), 1, 19, S("a2345678901234567890bcde"));
376    test(S("abcde"), 1, S("12345678901234567890"), 1, 20, S("a2345678901234567890bcde"));
377    test(S("abcde"), 1, S("12345678901234567890"), 10, 0, S("abcde"));
378    test(S("abcde"), 1, S("12345678901234567890"), 10, 1, S("a1bcde"));
379    test(S("abcde"), 1, S("12345678901234567890"), 10, 5, S("a12345bcde"));
380    test(S("abcde"), 1, S("12345678901234567890"), 10, 9, S("a123456789bcde"));
381    test(S("abcde"), 1, S("12345678901234567890"), 10, 10, S("a1234567890bcde"));
382    test(S("abcde"), 1, S("12345678901234567890"), 10, 11, S("a1234567890bcde"));
383    test(S("abcde"), 1, S("12345678901234567890"), 19, 0, S("abcde"));
384    test(S("abcde"), 1, S("12345678901234567890"), 19, 1, S("a0bcde"));
385    test(S("abcde"), 1, S("12345678901234567890"), 19, 2, S("a0bcde"));
386    test(S("abcde"), 1, S("12345678901234567890"), 20, 0, S("abcde"));
387    test(S("abcde"), 1, S("12345678901234567890"), 20, 1, S("abcde"));
388    test(S("abcde"), 1, S("12345678901234567890"), 21, 0, S("can't happen"));
389    test(S("abcde"), 2, S(""), 0, 0, S("abcde"));
390    test(S("abcde"), 2, S(""), 0, 1, S("abcde"));
391    test(S("abcde"), 2, S(""), 1, 0, S("can't happen"));
392    test(S("abcde"), 2, S("12345"), 0, 0, S("abcde"));
393}
394
395template <class S>
396void test6()
397{
398    test(S("abcde"), 2, S("12345"), 0, 1, S("ab1cde"));
399    test(S("abcde"), 2, S("12345"), 0, 2, S("ab12cde"));
400    test(S("abcde"), 2, S("12345"), 0, 4, S("ab1234cde"));
401    test(S("abcde"), 2, S("12345"), 0, 5, S("ab12345cde"));
402    test(S("abcde"), 2, S("12345"), 0, 6, S("ab12345cde"));
403    test(S("abcde"), 2, S("12345"), 1, 0, S("abcde"));
404    test(S("abcde"), 2, S("12345"), 1, 1, S("ab2cde"));
405    test(S("abcde"), 2, S("12345"), 1, 2, S("ab23cde"));
406    test(S("abcde"), 2, S("12345"), 1, 3, S("ab234cde"));
407    test(S("abcde"), 2, S("12345"), 1, 4, S("ab2345cde"));
408    test(S("abcde"), 2, S("12345"), 1, 5, S("ab2345cde"));
409    test(S("abcde"), 2, S("12345"), 2, 0, S("abcde"));
410    test(S("abcde"), 2, S("12345"), 2, 1, S("ab3cde"));
411    test(S("abcde"), 2, S("12345"), 2, 2, S("ab34cde"));
412    test(S("abcde"), 2, S("12345"), 2, 3, S("ab345cde"));
413    test(S("abcde"), 2, S("12345"), 2, 4, S("ab345cde"));
414    test(S("abcde"), 2, S("12345"), 4, 0, S("abcde"));
415    test(S("abcde"), 2, S("12345"), 4, 1, S("ab5cde"));
416    test(S("abcde"), 2, S("12345"), 4, 2, S("ab5cde"));
417    test(S("abcde"), 2, S("12345"), 5, 0, S("abcde"));
418    test(S("abcde"), 2, S("12345"), 5, 1, S("abcde"));
419    test(S("abcde"), 2, S("12345"), 6, 0, S("can't happen"));
420    test(S("abcde"), 2, S("1234567890"), 0, 0, S("abcde"));
421    test(S("abcde"), 2, S("1234567890"), 0, 1, S("ab1cde"));
422    test(S("abcde"), 2, S("1234567890"), 0, 5, S("ab12345cde"));
423    test(S("abcde"), 2, S("1234567890"), 0, 9, S("ab123456789cde"));
424    test(S("abcde"), 2, S("1234567890"), 0, 10, S("ab1234567890cde"));
425    test(S("abcde"), 2, S("1234567890"), 0, 11, S("ab1234567890cde"));
426    test(S("abcde"), 2, S("1234567890"), 1, 0, S("abcde"));
427    test(S("abcde"), 2, S("1234567890"), 1, 1, S("ab2cde"));
428    test(S("abcde"), 2, S("1234567890"), 1, 4, S("ab2345cde"));
429    test(S("abcde"), 2, S("1234567890"), 1, 8, S("ab23456789cde"));
430    test(S("abcde"), 2, S("1234567890"), 1, 9, S("ab234567890cde"));
431    test(S("abcde"), 2, S("1234567890"), 1, 10, S("ab234567890cde"));
432    test(S("abcde"), 2, S("1234567890"), 5, 0, S("abcde"));
433    test(S("abcde"), 2, S("1234567890"), 5, 1, S("ab6cde"));
434    test(S("abcde"), 2, S("1234567890"), 5, 2, S("ab67cde"));
435    test(S("abcde"), 2, S("1234567890"), 5, 4, S("ab6789cde"));
436    test(S("abcde"), 2, S("1234567890"), 5, 5, S("ab67890cde"));
437    test(S("abcde"), 2, S("1234567890"), 5, 6, S("ab67890cde"));
438    test(S("abcde"), 2, S("1234567890"), 9, 0, S("abcde"));
439    test(S("abcde"), 2, S("1234567890"), 9, 1, S("ab0cde"));
440    test(S("abcde"), 2, S("1234567890"), 9, 2, S("ab0cde"));
441    test(S("abcde"), 2, S("1234567890"), 10, 0, S("abcde"));
442    test(S("abcde"), 2, S("1234567890"), 10, 1, S("abcde"));
443    test(S("abcde"), 2, S("1234567890"), 11, 0, S("can't happen"));
444    test(S("abcde"), 2, S("12345678901234567890"), 0, 0, S("abcde"));
445    test(S("abcde"), 2, S("12345678901234567890"), 0, 1, S("ab1cde"));
446    test(S("abcde"), 2, S("12345678901234567890"), 0, 10, S("ab1234567890cde"));
447    test(S("abcde"), 2, S("12345678901234567890"), 0, 19, S("ab1234567890123456789cde"));
448}
449
450template <class S>
451void test7()
452{
453    test(S("abcde"), 2, S("12345678901234567890"), 0, 20, S("ab12345678901234567890cde"));
454    test(S("abcde"), 2, S("12345678901234567890"), 0, 21, S("ab12345678901234567890cde"));
455    test(S("abcde"), 2, S("12345678901234567890"), 1, 0, S("abcde"));
456    test(S("abcde"), 2, S("12345678901234567890"), 1, 1, S("ab2cde"));
457    test(S("abcde"), 2, S("12345678901234567890"), 1, 9, S("ab234567890cde"));
458    test(S("abcde"), 2, S("12345678901234567890"), 1, 18, S("ab234567890123456789cde"));
459    test(S("abcde"), 2, S("12345678901234567890"), 1, 19, S("ab2345678901234567890cde"));
460    test(S("abcde"), 2, S("12345678901234567890"), 1, 20, S("ab2345678901234567890cde"));
461    test(S("abcde"), 2, S("12345678901234567890"), 10, 0, S("abcde"));
462    test(S("abcde"), 2, S("12345678901234567890"), 10, 1, S("ab1cde"));
463    test(S("abcde"), 2, S("12345678901234567890"), 10, 5, S("ab12345cde"));
464    test(S("abcde"), 2, S("12345678901234567890"), 10, 9, S("ab123456789cde"));
465    test(S("abcde"), 2, S("12345678901234567890"), 10, 10, S("ab1234567890cde"));
466    test(S("abcde"), 2, S("12345678901234567890"), 10, 11, S("ab1234567890cde"));
467    test(S("abcde"), 2, S("12345678901234567890"), 19, 0, S("abcde"));
468    test(S("abcde"), 2, S("12345678901234567890"), 19, 1, S("ab0cde"));
469    test(S("abcde"), 2, S("12345678901234567890"), 19, 2, S("ab0cde"));
470    test(S("abcde"), 2, S("12345678901234567890"), 20, 0, S("abcde"));
471    test(S("abcde"), 2, S("12345678901234567890"), 20, 1, S("abcde"));
472    test(S("abcde"), 2, S("12345678901234567890"), 21, 0, S("can't happen"));
473    test(S("abcde"), 4, S(""), 0, 0, S("abcde"));
474    test(S("abcde"), 4, S(""), 0, 1, S("abcde"));
475    test(S("abcde"), 4, S(""), 1, 0, S("can't happen"));
476    test(S("abcde"), 4, S("12345"), 0, 0, S("abcde"));
477    test(S("abcde"), 4, S("12345"), 0, 1, S("abcd1e"));
478    test(S("abcde"), 4, S("12345"), 0, 2, S("abcd12e"));
479    test(S("abcde"), 4, S("12345"), 0, 4, S("abcd1234e"));
480    test(S("abcde"), 4, S("12345"), 0, 5, S("abcd12345e"));
481    test(S("abcde"), 4, S("12345"), 0, 6, S("abcd12345e"));
482    test(S("abcde"), 4, S("12345"), 1, 0, S("abcde"));
483    test(S("abcde"), 4, S("12345"), 1, 1, S("abcd2e"));
484    test(S("abcde"), 4, S("12345"), 1, 2, S("abcd23e"));
485    test(S("abcde"), 4, S("12345"), 1, 3, S("abcd234e"));
486    test(S("abcde"), 4, S("12345"), 1, 4, S("abcd2345e"));
487    test(S("abcde"), 4, S("12345"), 1, 5, S("abcd2345e"));
488    test(S("abcde"), 4, S("12345"), 2, 0, S("abcde"));
489    test(S("abcde"), 4, S("12345"), 2, 1, S("abcd3e"));
490    test(S("abcde"), 4, S("12345"), 2, 2, S("abcd34e"));
491    test(S("abcde"), 4, S("12345"), 2, 3, S("abcd345e"));
492    test(S("abcde"), 4, S("12345"), 2, 4, S("abcd345e"));
493    test(S("abcde"), 4, S("12345"), 4, 0, S("abcde"));
494    test(S("abcde"), 4, S("12345"), 4, 1, S("abcd5e"));
495    test(S("abcde"), 4, S("12345"), 4, 2, S("abcd5e"));
496    test(S("abcde"), 4, S("12345"), 5, 0, S("abcde"));
497    test(S("abcde"), 4, S("12345"), 5, 1, S("abcde"));
498    test(S("abcde"), 4, S("12345"), 6, 0, S("can't happen"));
499    test(S("abcde"), 4, S("1234567890"), 0, 0, S("abcde"));
500    test(S("abcde"), 4, S("1234567890"), 0, 1, S("abcd1e"));
501    test(S("abcde"), 4, S("1234567890"), 0, 5, S("abcd12345e"));
502    test(S("abcde"), 4, S("1234567890"), 0, 9, S("abcd123456789e"));
503}
504
505template <class S>
506void test8()
507{
508    test(S("abcde"), 4, S("1234567890"), 0, 10, S("abcd1234567890e"));
509    test(S("abcde"), 4, S("1234567890"), 0, 11, S("abcd1234567890e"));
510    test(S("abcde"), 4, S("1234567890"), 1, 0, S("abcde"));
511    test(S("abcde"), 4, S("1234567890"), 1, 1, S("abcd2e"));
512    test(S("abcde"), 4, S("1234567890"), 1, 4, S("abcd2345e"));
513    test(S("abcde"), 4, S("1234567890"), 1, 8, S("abcd23456789e"));
514    test(S("abcde"), 4, S("1234567890"), 1, 9, S("abcd234567890e"));
515    test(S("abcde"), 4, S("1234567890"), 1, 10, S("abcd234567890e"));
516    test(S("abcde"), 4, S("1234567890"), 5, 0, S("abcde"));
517    test(S("abcde"), 4, S("1234567890"), 5, 1, S("abcd6e"));
518    test(S("abcde"), 4, S("1234567890"), 5, 2, S("abcd67e"));
519    test(S("abcde"), 4, S("1234567890"), 5, 4, S("abcd6789e"));
520    test(S("abcde"), 4, S("1234567890"), 5, 5, S("abcd67890e"));
521    test(S("abcde"), 4, S("1234567890"), 5, 6, S("abcd67890e"));
522    test(S("abcde"), 4, S("1234567890"), 9, 0, S("abcde"));
523    test(S("abcde"), 4, S("1234567890"), 9, 1, S("abcd0e"));
524    test(S("abcde"), 4, S("1234567890"), 9, 2, S("abcd0e"));
525    test(S("abcde"), 4, S("1234567890"), 10, 0, S("abcde"));
526    test(S("abcde"), 4, S("1234567890"), 10, 1, S("abcde"));
527    test(S("abcde"), 4, S("1234567890"), 11, 0, S("can't happen"));
528    test(S("abcde"), 4, S("12345678901234567890"), 0, 0, S("abcde"));
529    test(S("abcde"), 4, S("12345678901234567890"), 0, 1, S("abcd1e"));
530    test(S("abcde"), 4, S("12345678901234567890"), 0, 10, S("abcd1234567890e"));
531    test(S("abcde"), 4, S("12345678901234567890"), 0, 19, S("abcd1234567890123456789e"));
532    test(S("abcde"), 4, S("12345678901234567890"), 0, 20, S("abcd12345678901234567890e"));
533    test(S("abcde"), 4, S("12345678901234567890"), 0, 21, S("abcd12345678901234567890e"));
534    test(S("abcde"), 4, S("12345678901234567890"), 1, 0, S("abcde"));
535    test(S("abcde"), 4, S("12345678901234567890"), 1, 1, S("abcd2e"));
536    test(S("abcde"), 4, S("12345678901234567890"), 1, 9, S("abcd234567890e"));
537    test(S("abcde"), 4, S("12345678901234567890"), 1, 18, S("abcd234567890123456789e"));
538    test(S("abcde"), 4, S("12345678901234567890"), 1, 19, S("abcd2345678901234567890e"));
539    test(S("abcde"), 4, S("12345678901234567890"), 1, 20, S("abcd2345678901234567890e"));
540    test(S("abcde"), 4, S("12345678901234567890"), 10, 0, S("abcde"));
541    test(S("abcde"), 4, S("12345678901234567890"), 10, 1, S("abcd1e"));
542    test(S("abcde"), 4, S("12345678901234567890"), 10, 5, S("abcd12345e"));
543    test(S("abcde"), 4, S("12345678901234567890"), 10, 9, S("abcd123456789e"));
544    test(S("abcde"), 4, S("12345678901234567890"), 10, 10, S("abcd1234567890e"));
545    test(S("abcde"), 4, S("12345678901234567890"), 10, 11, S("abcd1234567890e"));
546    test(S("abcde"), 4, S("12345678901234567890"), 19, 0, S("abcde"));
547    test(S("abcde"), 4, S("12345678901234567890"), 19, 1, S("abcd0e"));
548    test(S("abcde"), 4, S("12345678901234567890"), 19, 2, S("abcd0e"));
549    test(S("abcde"), 4, S("12345678901234567890"), 20, 0, S("abcde"));
550    test(S("abcde"), 4, S("12345678901234567890"), 20, 1, S("abcde"));
551    test(S("abcde"), 4, S("12345678901234567890"), 21, 0, S("can't happen"));
552    test(S("abcde"), 5, S(""), 0, 0, S("abcde"));
553    test(S("abcde"), 5, S(""), 0, 1, S("abcde"));
554    test(S("abcde"), 5, S(""), 1, 0, S("can't happen"));
555    test(S("abcde"), 5, S("12345"), 0, 0, S("abcde"));
556    test(S("abcde"), 5, S("12345"), 0, 1, S("abcde1"));
557    test(S("abcde"), 5, S("12345"), 0, 2, S("abcde12"));
558}
559
560template <class S>
561void test9()
562{
563    test(S("abcde"), 5, S("12345"), 0, 4, S("abcde1234"));
564    test(S("abcde"), 5, S("12345"), 0, 5, S("abcde12345"));
565    test(S("abcde"), 5, S("12345"), 0, 6, S("abcde12345"));
566    test(S("abcde"), 5, S("12345"), 1, 0, S("abcde"));
567    test(S("abcde"), 5, S("12345"), 1, 1, S("abcde2"));
568    test(S("abcde"), 5, S("12345"), 1, 2, S("abcde23"));
569    test(S("abcde"), 5, S("12345"), 1, 3, S("abcde234"));
570    test(S("abcde"), 5, S("12345"), 1, 4, S("abcde2345"));
571    test(S("abcde"), 5, S("12345"), 1, 5, S("abcde2345"));
572    test(S("abcde"), 5, S("12345"), 2, 0, S("abcde"));
573    test(S("abcde"), 5, S("12345"), 2, 1, S("abcde3"));
574    test(S("abcde"), 5, S("12345"), 2, 2, S("abcde34"));
575    test(S("abcde"), 5, S("12345"), 2, 3, S("abcde345"));
576    test(S("abcde"), 5, S("12345"), 2, 4, S("abcde345"));
577    test(S("abcde"), 5, S("12345"), 4, 0, S("abcde"));
578    test(S("abcde"), 5, S("12345"), 4, 1, S("abcde5"));
579    test(S("abcde"), 5, S("12345"), 4, 2, S("abcde5"));
580    test(S("abcde"), 5, S("12345"), 5, 0, S("abcde"));
581    test(S("abcde"), 5, S("12345"), 5, 1, S("abcde"));
582    test(S("abcde"), 5, S("12345"), 6, 0, S("can't happen"));
583    test(S("abcde"), 5, S("1234567890"), 0, 0, S("abcde"));
584    test(S("abcde"), 5, S("1234567890"), 0, 1, S("abcde1"));
585    test(S("abcde"), 5, S("1234567890"), 0, 5, S("abcde12345"));
586    test(S("abcde"), 5, S("1234567890"), 0, 9, S("abcde123456789"));
587    test(S("abcde"), 5, S("1234567890"), 0, 10, S("abcde1234567890"));
588    test(S("abcde"), 5, S("1234567890"), 0, 11, S("abcde1234567890"));
589    test(S("abcde"), 5, S("1234567890"), 1, 0, S("abcde"));
590    test(S("abcde"), 5, S("1234567890"), 1, 1, S("abcde2"));
591    test(S("abcde"), 5, S("1234567890"), 1, 4, S("abcde2345"));
592    test(S("abcde"), 5, S("1234567890"), 1, 8, S("abcde23456789"));
593    test(S("abcde"), 5, S("1234567890"), 1, 9, S("abcde234567890"));
594    test(S("abcde"), 5, S("1234567890"), 1, 10, S("abcde234567890"));
595    test(S("abcde"), 5, S("1234567890"), 5, 0, S("abcde"));
596    test(S("abcde"), 5, S("1234567890"), 5, 1, S("abcde6"));
597    test(S("abcde"), 5, S("1234567890"), 5, 2, S("abcde67"));
598    test(S("abcde"), 5, S("1234567890"), 5, 4, S("abcde6789"));
599    test(S("abcde"), 5, S("1234567890"), 5, 5, S("abcde67890"));
600    test(S("abcde"), 5, S("1234567890"), 5, 6, S("abcde67890"));
601    test(S("abcde"), 5, S("1234567890"), 9, 0, S("abcde"));
602    test(S("abcde"), 5, S("1234567890"), 9, 1, S("abcde0"));
603    test(S("abcde"), 5, S("1234567890"), 9, 2, S("abcde0"));
604    test(S("abcde"), 5, S("1234567890"), 10, 0, S("abcde"));
605    test(S("abcde"), 5, S("1234567890"), 10, 1, S("abcde"));
606    test(S("abcde"), 5, S("1234567890"), 11, 0, S("can't happen"));
607    test(S("abcde"), 5, S("12345678901234567890"), 0, 0, S("abcde"));
608    test(S("abcde"), 5, S("12345678901234567890"), 0, 1, S("abcde1"));
609    test(S("abcde"), 5, S("12345678901234567890"), 0, 10, S("abcde1234567890"));
610    test(S("abcde"), 5, S("12345678901234567890"), 0, 19, S("abcde1234567890123456789"));
611    test(S("abcde"), 5, S("12345678901234567890"), 0, 20, S("abcde12345678901234567890"));
612    test(S("abcde"), 5, S("12345678901234567890"), 0, 21, S("abcde12345678901234567890"));
613}
614
615template <class S>
616void test10()
617{
618    test(S("abcde"), 5, S("12345678901234567890"), 1, 0, S("abcde"));
619    test(S("abcde"), 5, S("12345678901234567890"), 1, 1, S("abcde2"));
620    test(S("abcde"), 5, S("12345678901234567890"), 1, 9, S("abcde234567890"));
621    test(S("abcde"), 5, S("12345678901234567890"), 1, 18, S("abcde234567890123456789"));
622    test(S("abcde"), 5, S("12345678901234567890"), 1, 19, S("abcde2345678901234567890"));
623    test(S("abcde"), 5, S("12345678901234567890"), 1, 20, S("abcde2345678901234567890"));
624    test(S("abcde"), 5, S("12345678901234567890"), 10, 0, S("abcde"));
625    test(S("abcde"), 5, S("12345678901234567890"), 10, 1, S("abcde1"));
626    test(S("abcde"), 5, S("12345678901234567890"), 10, 5, S("abcde12345"));
627    test(S("abcde"), 5, S("12345678901234567890"), 10, 9, S("abcde123456789"));
628    test(S("abcde"), 5, S("12345678901234567890"), 10, 10, S("abcde1234567890"));
629    test(S("abcde"), 5, S("12345678901234567890"), 10, 11, S("abcde1234567890"));
630    test(S("abcde"), 5, S("12345678901234567890"), 19, 0, S("abcde"));
631    test(S("abcde"), 5, S("12345678901234567890"), 19, 1, S("abcde0"));
632    test(S("abcde"), 5, S("12345678901234567890"), 19, 2, S("abcde0"));
633    test(S("abcde"), 5, S("12345678901234567890"), 20, 0, S("abcde"));
634    test(S("abcde"), 5, S("12345678901234567890"), 20, 1, S("abcde"));
635    test(S("abcde"), 5, S("12345678901234567890"), 21, 0, S("can't happen"));
636    test(S("abcde"), 6, S(""), 0, 0, S("can't happen"));
637    test(S("abcde"), 6, S(""), 0, 1, S("can't happen"));
638    test(S("abcde"), 6, S(""), 1, 0, S("can't happen"));
639    test(S("abcde"), 6, S("12345"), 0, 0, S("can't happen"));
640    test(S("abcde"), 6, S("12345"), 0, 1, S("can't happen"));
641    test(S("abcde"), 6, S("12345"), 0, 2, S("can't happen"));
642    test(S("abcde"), 6, S("12345"), 0, 4, S("can't happen"));
643    test(S("abcde"), 6, S("12345"), 0, 5, S("can't happen"));
644    test(S("abcde"), 6, S("12345"), 0, 6, S("can't happen"));
645    test(S("abcde"), 6, S("12345"), 1, 0, S("can't happen"));
646    test(S("abcde"), 6, S("12345"), 1, 1, S("can't happen"));
647    test(S("abcde"), 6, S("12345"), 1, 2, S("can't happen"));
648    test(S("abcde"), 6, S("12345"), 1, 3, S("can't happen"));
649    test(S("abcde"), 6, S("12345"), 1, 4, S("can't happen"));
650    test(S("abcde"), 6, S("12345"), 1, 5, S("can't happen"));
651    test(S("abcde"), 6, S("12345"), 2, 0, S("can't happen"));
652    test(S("abcde"), 6, S("12345"), 2, 1, S("can't happen"));
653    test(S("abcde"), 6, S("12345"), 2, 2, S("can't happen"));
654    test(S("abcde"), 6, S("12345"), 2, 3, S("can't happen"));
655    test(S("abcde"), 6, S("12345"), 2, 4, S("can't happen"));
656    test(S("abcde"), 6, S("12345"), 4, 0, S("can't happen"));
657    test(S("abcde"), 6, S("12345"), 4, 1, S("can't happen"));
658    test(S("abcde"), 6, S("12345"), 4, 2, S("can't happen"));
659    test(S("abcde"), 6, S("12345"), 5, 0, S("can't happen"));
660    test(S("abcde"), 6, S("12345"), 5, 1, S("can't happen"));
661    test(S("abcde"), 6, S("12345"), 6, 0, S("can't happen"));
662    test(S("abcde"), 6, S("1234567890"), 0, 0, S("can't happen"));
663    test(S("abcde"), 6, S("1234567890"), 0, 1, S("can't happen"));
664    test(S("abcde"), 6, S("1234567890"), 0, 5, S("can't happen"));
665    test(S("abcde"), 6, S("1234567890"), 0, 9, S("can't happen"));
666    test(S("abcde"), 6, S("1234567890"), 0, 10, S("can't happen"));
667    test(S("abcde"), 6, S("1234567890"), 0, 11, S("can't happen"));
668}
669
670template <class S>
671void test11()
672{
673    test(S("abcde"), 6, S("1234567890"), 1, 0, S("can't happen"));
674    test(S("abcde"), 6, S("1234567890"), 1, 1, S("can't happen"));
675    test(S("abcde"), 6, S("1234567890"), 1, 4, S("can't happen"));
676    test(S("abcde"), 6, S("1234567890"), 1, 8, S("can't happen"));
677    test(S("abcde"), 6, S("1234567890"), 1, 9, S("can't happen"));
678    test(S("abcde"), 6, S("1234567890"), 1, 10, S("can't happen"));
679    test(S("abcde"), 6, S("1234567890"), 5, 0, S("can't happen"));
680    test(S("abcde"), 6, S("1234567890"), 5, 1, S("can't happen"));
681    test(S("abcde"), 6, S("1234567890"), 5, 2, S("can't happen"));
682    test(S("abcde"), 6, S("1234567890"), 5, 4, S("can't happen"));
683    test(S("abcde"), 6, S("1234567890"), 5, 5, S("can't happen"));
684    test(S("abcde"), 6, S("1234567890"), 5, 6, S("can't happen"));
685    test(S("abcde"), 6, S("1234567890"), 9, 0, S("can't happen"));
686    test(S("abcde"), 6, S("1234567890"), 9, 1, S("can't happen"));
687    test(S("abcde"), 6, S("1234567890"), 9, 2, S("can't happen"));
688    test(S("abcde"), 6, S("1234567890"), 10, 0, S("can't happen"));
689    test(S("abcde"), 6, S("1234567890"), 10, 1, S("can't happen"));
690    test(S("abcde"), 6, S("1234567890"), 11, 0, S("can't happen"));
691    test(S("abcde"), 6, S("12345678901234567890"), 0, 0, S("can't happen"));
692    test(S("abcde"), 6, S("12345678901234567890"), 0, 1, S("can't happen"));
693    test(S("abcde"), 6, S("12345678901234567890"), 0, 10, S("can't happen"));
694    test(S("abcde"), 6, S("12345678901234567890"), 0, 19, S("can't happen"));
695    test(S("abcde"), 6, S("12345678901234567890"), 0, 20, S("can't happen"));
696    test(S("abcde"), 6, S("12345678901234567890"), 0, 21, S("can't happen"));
697    test(S("abcde"), 6, S("12345678901234567890"), 1, 0, S("can't happen"));
698    test(S("abcde"), 6, S("12345678901234567890"), 1, 1, S("can't happen"));
699    test(S("abcde"), 6, S("12345678901234567890"), 1, 9, S("can't happen"));
700    test(S("abcde"), 6, S("12345678901234567890"), 1, 18, S("can't happen"));
701    test(S("abcde"), 6, S("12345678901234567890"), 1, 19, S("can't happen"));
702    test(S("abcde"), 6, S("12345678901234567890"), 1, 20, S("can't happen"));
703    test(S("abcde"), 6, S("12345678901234567890"), 10, 0, S("can't happen"));
704    test(S("abcde"), 6, S("12345678901234567890"), 10, 1, S("can't happen"));
705    test(S("abcde"), 6, S("12345678901234567890"), 10, 5, S("can't happen"));
706    test(S("abcde"), 6, S("12345678901234567890"), 10, 9, S("can't happen"));
707    test(S("abcde"), 6, S("12345678901234567890"), 10, 10, S("can't happen"));
708    test(S("abcde"), 6, S("12345678901234567890"), 10, 11, S("can't happen"));
709    test(S("abcde"), 6, S("12345678901234567890"), 19, 0, S("can't happen"));
710    test(S("abcde"), 6, S("12345678901234567890"), 19, 1, S("can't happen"));
711    test(S("abcde"), 6, S("12345678901234567890"), 19, 2, S("can't happen"));
712    test(S("abcde"), 6, S("12345678901234567890"), 20, 0, S("can't happen"));
713    test(S("abcde"), 6, S("12345678901234567890"), 20, 1, S("can't happen"));
714    test(S("abcde"), 6, S("12345678901234567890"), 21, 0, S("can't happen"));
715    test(S("abcdefghij"), 0, S(""), 0, 0, S("abcdefghij"));
716    test(S("abcdefghij"), 0, S(""), 0, 1, S("abcdefghij"));
717    test(S("abcdefghij"), 0, S(""), 1, 0, S("can't happen"));
718    test(S("abcdefghij"), 0, S("12345"), 0, 0, S("abcdefghij"));
719    test(S("abcdefghij"), 0, S("12345"), 0, 1, S("1abcdefghij"));
720    test(S("abcdefghij"), 0, S("12345"), 0, 2, S("12abcdefghij"));
721    test(S("abcdefghij"), 0, S("12345"), 0, 4, S("1234abcdefghij"));
722    test(S("abcdefghij"), 0, S("12345"), 0, 5, S("12345abcdefghij"));
723}
724
725template <class S>
726void test12()
727{
728    test(S("abcdefghij"), 0, S("12345"), 0, 6, S("12345abcdefghij"));
729    test(S("abcdefghij"), 0, S("12345"), 1, 0, S("abcdefghij"));
730    test(S("abcdefghij"), 0, S("12345"), 1, 1, S("2abcdefghij"));
731    test(S("abcdefghij"), 0, S("12345"), 1, 2, S("23abcdefghij"));
732    test(S("abcdefghij"), 0, S("12345"), 1, 3, S("234abcdefghij"));
733    test(S("abcdefghij"), 0, S("12345"), 1, 4, S("2345abcdefghij"));
734    test(S("abcdefghij"), 0, S("12345"), 1, 5, S("2345abcdefghij"));
735    test(S("abcdefghij"), 0, S("12345"), 2, 0, S("abcdefghij"));
736    test(S("abcdefghij"), 0, S("12345"), 2, 1, S("3abcdefghij"));
737    test(S("abcdefghij"), 0, S("12345"), 2, 2, S("34abcdefghij"));
738    test(S("abcdefghij"), 0, S("12345"), 2, 3, S("345abcdefghij"));
739    test(S("abcdefghij"), 0, S("12345"), 2, 4, S("345abcdefghij"));
740    test(S("abcdefghij"), 0, S("12345"), 4, 0, S("abcdefghij"));
741    test(S("abcdefghij"), 0, S("12345"), 4, 1, S("5abcdefghij"));
742    test(S("abcdefghij"), 0, S("12345"), 4, 2, S("5abcdefghij"));
743    test(S("abcdefghij"), 0, S("12345"), 5, 0, S("abcdefghij"));
744    test(S("abcdefghij"), 0, S("12345"), 5, 1, S("abcdefghij"));
745    test(S("abcdefghij"), 0, S("12345"), 6, 0, S("can't happen"));
746    test(S("abcdefghij"), 0, S("1234567890"), 0, 0, S("abcdefghij"));
747    test(S("abcdefghij"), 0, S("1234567890"), 0, 1, S("1abcdefghij"));
748    test(S("abcdefghij"), 0, S("1234567890"), 0, 5, S("12345abcdefghij"));
749    test(S("abcdefghij"), 0, S("1234567890"), 0, 9, S("123456789abcdefghij"));
750    test(S("abcdefghij"), 0, S("1234567890"), 0, 10, S("1234567890abcdefghij"));
751    test(S("abcdefghij"), 0, S("1234567890"), 0, 11, S("1234567890abcdefghij"));
752    test(S("abcdefghij"), 0, S("1234567890"), 1, 0, S("abcdefghij"));
753    test(S("abcdefghij"), 0, S("1234567890"), 1, 1, S("2abcdefghij"));
754    test(S("abcdefghij"), 0, S("1234567890"), 1, 4, S("2345abcdefghij"));
755    test(S("abcdefghij"), 0, S("1234567890"), 1, 8, S("23456789abcdefghij"));
756    test(S("abcdefghij"), 0, S("1234567890"), 1, 9, S("234567890abcdefghij"));
757    test(S("abcdefghij"), 0, S("1234567890"), 1, 10, S("234567890abcdefghij"));
758    test(S("abcdefghij"), 0, S("1234567890"), 5, 0, S("abcdefghij"));
759    test(S("abcdefghij"), 0, S("1234567890"), 5, 1, S("6abcdefghij"));
760    test(S("abcdefghij"), 0, S("1234567890"), 5, 2, S("67abcdefghij"));
761    test(S("abcdefghij"), 0, S("1234567890"), 5, 4, S("6789abcdefghij"));
762    test(S("abcdefghij"), 0, S("1234567890"), 5, 5, S("67890abcdefghij"));
763    test(S("abcdefghij"), 0, S("1234567890"), 5, 6, S("67890abcdefghij"));
764    test(S("abcdefghij"), 0, S("1234567890"), 9, 0, S("abcdefghij"));
765    test(S("abcdefghij"), 0, S("1234567890"), 9, 1, S("0abcdefghij"));
766    test(S("abcdefghij"), 0, S("1234567890"), 9, 2, S("0abcdefghij"));
767    test(S("abcdefghij"), 0, S("1234567890"), 10, 0, S("abcdefghij"));
768    test(S("abcdefghij"), 0, S("1234567890"), 10, 1, S("abcdefghij"));
769    test(S("abcdefghij"), 0, S("1234567890"), 11, 0, S("can't happen"));
770    test(S("abcdefghij"), 0, S("12345678901234567890"), 0, 0, S("abcdefghij"));
771    test(S("abcdefghij"), 0, S("12345678901234567890"), 0, 1, S("1abcdefghij"));
772    test(S("abcdefghij"), 0, S("12345678901234567890"), 0, 10, S("1234567890abcdefghij"));
773    test(S("abcdefghij"), 0, S("12345678901234567890"), 0, 19, S("1234567890123456789abcdefghij"));
774    test(S("abcdefghij"), 0, S("12345678901234567890"), 0, 20, S("12345678901234567890abcdefghij"));
775    test(S("abcdefghij"), 0, S("12345678901234567890"), 0, 21, S("12345678901234567890abcdefghij"));
776    test(S("abcdefghij"), 0, S("12345678901234567890"), 1, 0, S("abcdefghij"));
777    test(S("abcdefghij"), 0, S("12345678901234567890"), 1, 1, S("2abcdefghij"));
778}
779
780template <class S>
781void test13()
782{
783    test(S("abcdefghij"), 0, S("12345678901234567890"), 1, 9, S("234567890abcdefghij"));
784    test(S("abcdefghij"), 0, S("12345678901234567890"), 1, 18, S("234567890123456789abcdefghij"));
785    test(S("abcdefghij"), 0, S("12345678901234567890"), 1, 19, S("2345678901234567890abcdefghij"));
786    test(S("abcdefghij"), 0, S("12345678901234567890"), 1, 20, S("2345678901234567890abcdefghij"));
787    test(S("abcdefghij"), 0, S("12345678901234567890"), 10, 0, S("abcdefghij"));
788    test(S("abcdefghij"), 0, S("12345678901234567890"), 10, 1, S("1abcdefghij"));
789    test(S("abcdefghij"), 0, S("12345678901234567890"), 10, 5, S("12345abcdefghij"));
790    test(S("abcdefghij"), 0, S("12345678901234567890"), 10, 9, S("123456789abcdefghij"));
791    test(S("abcdefghij"), 0, S("12345678901234567890"), 10, 10, S("1234567890abcdefghij"));
792    test(S("abcdefghij"), 0, S("12345678901234567890"), 10, 11, S("1234567890abcdefghij"));
793    test(S("abcdefghij"), 0, S("12345678901234567890"), 19, 0, S("abcdefghij"));
794    test(S("abcdefghij"), 0, S("12345678901234567890"), 19, 1, S("0abcdefghij"));
795    test(S("abcdefghij"), 0, S("12345678901234567890"), 19, 2, S("0abcdefghij"));
796    test(S("abcdefghij"), 0, S("12345678901234567890"), 20, 0, S("abcdefghij"));
797    test(S("abcdefghij"), 0, S("12345678901234567890"), 20, 1, S("abcdefghij"));
798    test(S("abcdefghij"), 0, S("12345678901234567890"), 21, 0, S("can't happen"));
799    test(S("abcdefghij"), 1, S(""), 0, 0, S("abcdefghij"));
800    test(S("abcdefghij"), 1, S(""), 0, 1, S("abcdefghij"));
801    test(S("abcdefghij"), 1, S(""), 1, 0, S("can't happen"));
802    test(S("abcdefghij"), 1, S("12345"), 0, 0, S("abcdefghij"));
803    test(S("abcdefghij"), 1, S("12345"), 0, 1, S("a1bcdefghij"));
804    test(S("abcdefghij"), 1, S("12345"), 0, 2, S("a12bcdefghij"));
805    test(S("abcdefghij"), 1, S("12345"), 0, 4, S("a1234bcdefghij"));
806    test(S("abcdefghij"), 1, S("12345"), 0, 5, S("a12345bcdefghij"));
807    test(S("abcdefghij"), 1, S("12345"), 0, 6, S("a12345bcdefghij"));
808    test(S("abcdefghij"), 1, S("12345"), 1, 0, S("abcdefghij"));
809    test(S("abcdefghij"), 1, S("12345"), 1, 1, S("a2bcdefghij"));
810    test(S("abcdefghij"), 1, S("12345"), 1, 2, S("a23bcdefghij"));
811    test(S("abcdefghij"), 1, S("12345"), 1, 3, S("a234bcdefghij"));
812    test(S("abcdefghij"), 1, S("12345"), 1, 4, S("a2345bcdefghij"));
813    test(S("abcdefghij"), 1, S("12345"), 1, 5, S("a2345bcdefghij"));
814    test(S("abcdefghij"), 1, S("12345"), 2, 0, S("abcdefghij"));
815    test(S("abcdefghij"), 1, S("12345"), 2, 1, S("a3bcdefghij"));
816    test(S("abcdefghij"), 1, S("12345"), 2, 2, S("a34bcdefghij"));
817    test(S("abcdefghij"), 1, S("12345"), 2, 3, S("a345bcdefghij"));
818    test(S("abcdefghij"), 1, S("12345"), 2, 4, S("a345bcdefghij"));
819    test(S("abcdefghij"), 1, S("12345"), 4, 0, S("abcdefghij"));
820    test(S("abcdefghij"), 1, S("12345"), 4, 1, S("a5bcdefghij"));
821    test(S("abcdefghij"), 1, S("12345"), 4, 2, S("a5bcdefghij"));
822    test(S("abcdefghij"), 1, S("12345"), 5, 0, S("abcdefghij"));
823    test(S("abcdefghij"), 1, S("12345"), 5, 1, S("abcdefghij"));
824    test(S("abcdefghij"), 1, S("12345"), 6, 0, S("can't happen"));
825    test(S("abcdefghij"), 1, S("1234567890"), 0, 0, S("abcdefghij"));
826    test(S("abcdefghij"), 1, S("1234567890"), 0, 1, S("a1bcdefghij"));
827    test(S("abcdefghij"), 1, S("1234567890"), 0, 5, S("a12345bcdefghij"));
828    test(S("abcdefghij"), 1, S("1234567890"), 0, 9, S("a123456789bcdefghij"));
829    test(S("abcdefghij"), 1, S("1234567890"), 0, 10, S("a1234567890bcdefghij"));
830    test(S("abcdefghij"), 1, S("1234567890"), 0, 11, S("a1234567890bcdefghij"));
831    test(S("abcdefghij"), 1, S("1234567890"), 1, 0, S("abcdefghij"));
832    test(S("abcdefghij"), 1, S("1234567890"), 1, 1, S("a2bcdefghij"));
833}
834
835template <class S>
836void test14()
837{
838    test(S("abcdefghij"), 1, S("1234567890"), 1, 4, S("a2345bcdefghij"));
839    test(S("abcdefghij"), 1, S("1234567890"), 1, 8, S("a23456789bcdefghij"));
840    test(S("abcdefghij"), 1, S("1234567890"), 1, 9, S("a234567890bcdefghij"));
841    test(S("abcdefghij"), 1, S("1234567890"), 1, 10, S("a234567890bcdefghij"));
842    test(S("abcdefghij"), 1, S("1234567890"), 5, 0, S("abcdefghij"));
843    test(S("abcdefghij"), 1, S("1234567890"), 5, 1, S("a6bcdefghij"));
844    test(S("abcdefghij"), 1, S("1234567890"), 5, 2, S("a67bcdefghij"));
845    test(S("abcdefghij"), 1, S("1234567890"), 5, 4, S("a6789bcdefghij"));
846    test(S("abcdefghij"), 1, S("1234567890"), 5, 5, S("a67890bcdefghij"));
847    test(S("abcdefghij"), 1, S("1234567890"), 5, 6, S("a67890bcdefghij"));
848    test(S("abcdefghij"), 1, S("1234567890"), 9, 0, S("abcdefghij"));
849    test(S("abcdefghij"), 1, S("1234567890"), 9, 1, S("a0bcdefghij"));
850    test(S("abcdefghij"), 1, S("1234567890"), 9, 2, S("a0bcdefghij"));
851    test(S("abcdefghij"), 1, S("1234567890"), 10, 0, S("abcdefghij"));
852    test(S("abcdefghij"), 1, S("1234567890"), 10, 1, S("abcdefghij"));
853    test(S("abcdefghij"), 1, S("1234567890"), 11, 0, S("can't happen"));
854    test(S("abcdefghij"), 1, S("12345678901234567890"), 0, 0, S("abcdefghij"));
855    test(S("abcdefghij"), 1, S("12345678901234567890"), 0, 1, S("a1bcdefghij"));
856    test(S("abcdefghij"), 1, S("12345678901234567890"), 0, 10, S("a1234567890bcdefghij"));
857    test(S("abcdefghij"), 1, S("12345678901234567890"), 0, 19, S("a1234567890123456789bcdefghij"));
858    test(S("abcdefghij"), 1, S("12345678901234567890"), 0, 20, S("a12345678901234567890bcdefghij"));
859    test(S("abcdefghij"), 1, S("12345678901234567890"), 0, 21, S("a12345678901234567890bcdefghij"));
860    test(S("abcdefghij"), 1, S("12345678901234567890"), 1, 0, S("abcdefghij"));
861    test(S("abcdefghij"), 1, S("12345678901234567890"), 1, 1, S("a2bcdefghij"));
862    test(S("abcdefghij"), 1, S("12345678901234567890"), 1, 9, S("a234567890bcdefghij"));
863    test(S("abcdefghij"), 1, S("12345678901234567890"), 1, 18, S("a234567890123456789bcdefghij"));
864    test(S("abcdefghij"), 1, S("12345678901234567890"), 1, 19, S("a2345678901234567890bcdefghij"));
865    test(S("abcdefghij"), 1, S("12345678901234567890"), 1, 20, S("a2345678901234567890bcdefghij"));
866    test(S("abcdefghij"), 1, S("12345678901234567890"), 10, 0, S("abcdefghij"));
867    test(S("abcdefghij"), 1, S("12345678901234567890"), 10, 1, S("a1bcdefghij"));
868    test(S("abcdefghij"), 1, S("12345678901234567890"), 10, 5, S("a12345bcdefghij"));
869    test(S("abcdefghij"), 1, S("12345678901234567890"), 10, 9, S("a123456789bcdefghij"));
870    test(S("abcdefghij"), 1, S("12345678901234567890"), 10, 10, S("a1234567890bcdefghij"));
871    test(S("abcdefghij"), 1, S("12345678901234567890"), 10, 11, S("a1234567890bcdefghij"));
872    test(S("abcdefghij"), 1, S("12345678901234567890"), 19, 0, S("abcdefghij"));
873    test(S("abcdefghij"), 1, S("12345678901234567890"), 19, 1, S("a0bcdefghij"));
874    test(S("abcdefghij"), 1, S("12345678901234567890"), 19, 2, S("a0bcdefghij"));
875    test(S("abcdefghij"), 1, S("12345678901234567890"), 20, 0, S("abcdefghij"));
876    test(S("abcdefghij"), 1, S("12345678901234567890"), 20, 1, S("abcdefghij"));
877    test(S("abcdefghij"), 1, S("12345678901234567890"), 21, 0, S("can't happen"));
878    test(S("abcdefghij"), 5, S(""), 0, 0, S("abcdefghij"));
879    test(S("abcdefghij"), 5, S(""), 0, 1, S("abcdefghij"));
880    test(S("abcdefghij"), 5, S(""), 1, 0, S("can't happen"));
881    test(S("abcdefghij"), 5, S("12345"), 0, 0, S("abcdefghij"));
882    test(S("abcdefghij"), 5, S("12345"), 0, 1, S("abcde1fghij"));
883    test(S("abcdefghij"), 5, S("12345"), 0, 2, S("abcde12fghij"));
884    test(S("abcdefghij"), 5, S("12345"), 0, 4, S("abcde1234fghij"));
885    test(S("abcdefghij"), 5, S("12345"), 0, 5, S("abcde12345fghij"));
886    test(S("abcdefghij"), 5, S("12345"), 0, 6, S("abcde12345fghij"));
887    test(S("abcdefghij"), 5, S("12345"), 1, 0, S("abcdefghij"));
888}
889
890template <class S>
891void test15()
892{
893    test(S("abcdefghij"), 5, S("12345"), 1, 1, S("abcde2fghij"));
894    test(S("abcdefghij"), 5, S("12345"), 1, 2, S("abcde23fghij"));
895    test(S("abcdefghij"), 5, S("12345"), 1, 3, S("abcde234fghij"));
896    test(S("abcdefghij"), 5, S("12345"), 1, 4, S("abcde2345fghij"));
897    test(S("abcdefghij"), 5, S("12345"), 1, 5, S("abcde2345fghij"));
898    test(S("abcdefghij"), 5, S("12345"), 2, 0, S("abcdefghij"));
899    test(S("abcdefghij"), 5, S("12345"), 2, 1, S("abcde3fghij"));
900    test(S("abcdefghij"), 5, S("12345"), 2, 2, S("abcde34fghij"));
901    test(S("abcdefghij"), 5, S("12345"), 2, 3, S("abcde345fghij"));
902    test(S("abcdefghij"), 5, S("12345"), 2, 4, S("abcde345fghij"));
903    test(S("abcdefghij"), 5, S("12345"), 4, 0, S("abcdefghij"));
904    test(S("abcdefghij"), 5, S("12345"), 4, 1, S("abcde5fghij"));
905    test(S("abcdefghij"), 5, S("12345"), 4, 2, S("abcde5fghij"));
906    test(S("abcdefghij"), 5, S("12345"), 5, 0, S("abcdefghij"));
907    test(S("abcdefghij"), 5, S("12345"), 5, 1, S("abcdefghij"));
908    test(S("abcdefghij"), 5, S("12345"), 6, 0, S("can't happen"));
909    test(S("abcdefghij"), 5, S("1234567890"), 0, 0, S("abcdefghij"));
910    test(S("abcdefghij"), 5, S("1234567890"), 0, 1, S("abcde1fghij"));
911    test(S("abcdefghij"), 5, S("1234567890"), 0, 5, S("abcde12345fghij"));
912    test(S("abcdefghij"), 5, S("1234567890"), 0, 9, S("abcde123456789fghij"));
913    test(S("abcdefghij"), 5, S("1234567890"), 0, 10, S("abcde1234567890fghij"));
914    test(S("abcdefghij"), 5, S("1234567890"), 0, 11, S("abcde1234567890fghij"));
915    test(S("abcdefghij"), 5, S("1234567890"), 1, 0, S("abcdefghij"));
916    test(S("abcdefghij"), 5, S("1234567890"), 1, 1, S("abcde2fghij"));
917    test(S("abcdefghij"), 5, S("1234567890"), 1, 4, S("abcde2345fghij"));
918    test(S("abcdefghij"), 5, S("1234567890"), 1, 8, S("abcde23456789fghij"));
919    test(S("abcdefghij"), 5, S("1234567890"), 1, 9, S("abcde234567890fghij"));
920    test(S("abcdefghij"), 5, S("1234567890"), 1, 10, S("abcde234567890fghij"));
921    test(S("abcdefghij"), 5, S("1234567890"), 5, 0, S("abcdefghij"));
922    test(S("abcdefghij"), 5, S("1234567890"), 5, 1, S("abcde6fghij"));
923    test(S("abcdefghij"), 5, S("1234567890"), 5, 2, S("abcde67fghij"));
924    test(S("abcdefghij"), 5, S("1234567890"), 5, 4, S("abcde6789fghij"));
925    test(S("abcdefghij"), 5, S("1234567890"), 5, 5, S("abcde67890fghij"));
926    test(S("abcdefghij"), 5, S("1234567890"), 5, 6, S("abcde67890fghij"));
927    test(S("abcdefghij"), 5, S("1234567890"), 9, 0, S("abcdefghij"));
928    test(S("abcdefghij"), 5, S("1234567890"), 9, 1, S("abcde0fghij"));
929    test(S("abcdefghij"), 5, S("1234567890"), 9, 2, S("abcde0fghij"));
930    test(S("abcdefghij"), 5, S("1234567890"), 10, 0, S("abcdefghij"));
931    test(S("abcdefghij"), 5, S("1234567890"), 10, 1, S("abcdefghij"));
932    test(S("abcdefghij"), 5, S("1234567890"), 11, 0, S("can't happen"));
933    test(S("abcdefghij"), 5, S("12345678901234567890"), 0, 0, S("abcdefghij"));
934    test(S("abcdefghij"), 5, S("12345678901234567890"), 0, 1, S("abcde1fghij"));
935    test(S("abcdefghij"), 5, S("12345678901234567890"), 0, 10, S("abcde1234567890fghij"));
936    test(S("abcdefghij"), 5, S("12345678901234567890"), 0, 19, S("abcde1234567890123456789fghij"));
937    test(S("abcdefghij"), 5, S("12345678901234567890"), 0, 20, S("abcde12345678901234567890fghij"));
938    test(S("abcdefghij"), 5, S("12345678901234567890"), 0, 21, S("abcde12345678901234567890fghij"));
939    test(S("abcdefghij"), 5, S("12345678901234567890"), 1, 0, S("abcdefghij"));
940    test(S("abcdefghij"), 5, S("12345678901234567890"), 1, 1, S("abcde2fghij"));
941    test(S("abcdefghij"), 5, S("12345678901234567890"), 1, 9, S("abcde234567890fghij"));
942    test(S("abcdefghij"), 5, S("12345678901234567890"), 1, 18, S("abcde234567890123456789fghij"));
943}
944
945template <class S>
946void test16()
947{
948    test(S("abcdefghij"), 5, S("12345678901234567890"), 1, 19, S("abcde2345678901234567890fghij"));
949    test(S("abcdefghij"), 5, S("12345678901234567890"), 1, 20, S("abcde2345678901234567890fghij"));
950    test(S("abcdefghij"), 5, S("12345678901234567890"), 10, 0, S("abcdefghij"));
951    test(S("abcdefghij"), 5, S("12345678901234567890"), 10, 1, S("abcde1fghij"));
952    test(S("abcdefghij"), 5, S("12345678901234567890"), 10, 5, S("abcde12345fghij"));
953    test(S("abcdefghij"), 5, S("12345678901234567890"), 10, 9, S("abcde123456789fghij"));
954    test(S("abcdefghij"), 5, S("12345678901234567890"), 10, 10, S("abcde1234567890fghij"));
955    test(S("abcdefghij"), 5, S("12345678901234567890"), 10, 11, S("abcde1234567890fghij"));
956    test(S("abcdefghij"), 5, S("12345678901234567890"), 19, 0, S("abcdefghij"));
957    test(S("abcdefghij"), 5, S("12345678901234567890"), 19, 1, S("abcde0fghij"));
958    test(S("abcdefghij"), 5, S("12345678901234567890"), 19, 2, S("abcde0fghij"));
959    test(S("abcdefghij"), 5, S("12345678901234567890"), 20, 0, S("abcdefghij"));
960    test(S("abcdefghij"), 5, S("12345678901234567890"), 20, 1, S("abcdefghij"));
961    test(S("abcdefghij"), 5, S("12345678901234567890"), 21, 0, S("can't happen"));
962    test(S("abcdefghij"), 9, S(""), 0, 0, S("abcdefghij"));
963    test(S("abcdefghij"), 9, S(""), 0, 1, S("abcdefghij"));
964    test(S("abcdefghij"), 9, S(""), 1, 0, S("can't happen"));
965    test(S("abcdefghij"), 9, S("12345"), 0, 0, S("abcdefghij"));
966    test(S("abcdefghij"), 9, S("12345"), 0, 1, S("abcdefghi1j"));
967    test(S("abcdefghij"), 9, S("12345"), 0, 2, S("abcdefghi12j"));
968    test(S("abcdefghij"), 9, S("12345"), 0, 4, S("abcdefghi1234j"));
969    test(S("abcdefghij"), 9, S("12345"), 0, 5, S("abcdefghi12345j"));
970    test(S("abcdefghij"), 9, S("12345"), 0, 6, S("abcdefghi12345j"));
971    test(S("abcdefghij"), 9, S("12345"), 1, 0, S("abcdefghij"));
972    test(S("abcdefghij"), 9, S("12345"), 1, 1, S("abcdefghi2j"));
973    test(S("abcdefghij"), 9, S("12345"), 1, 2, S("abcdefghi23j"));
974    test(S("abcdefghij"), 9, S("12345"), 1, 3, S("abcdefghi234j"));
975    test(S("abcdefghij"), 9, S("12345"), 1, 4, S("abcdefghi2345j"));
976    test(S("abcdefghij"), 9, S("12345"), 1, 5, S("abcdefghi2345j"));
977    test(S("abcdefghij"), 9, S("12345"), 2, 0, S("abcdefghij"));
978    test(S("abcdefghij"), 9, S("12345"), 2, 1, S("abcdefghi3j"));
979    test(S("abcdefghij"), 9, S("12345"), 2, 2, S("abcdefghi34j"));
980    test(S("abcdefghij"), 9, S("12345"), 2, 3, S("abcdefghi345j"));
981    test(S("abcdefghij"), 9, S("12345"), 2, 4, S("abcdefghi345j"));
982    test(S("abcdefghij"), 9, S("12345"), 4, 0, S("abcdefghij"));
983    test(S("abcdefghij"), 9, S("12345"), 4, 1, S("abcdefghi5j"));
984    test(S("abcdefghij"), 9, S("12345"), 4, 2, S("abcdefghi5j"));
985    test(S("abcdefghij"), 9, S("12345"), 5, 0, S("abcdefghij"));
986    test(S("abcdefghij"), 9, S("12345"), 5, 1, S("abcdefghij"));
987    test(S("abcdefghij"), 9, S("12345"), 6, 0, S("can't happen"));
988    test(S("abcdefghij"), 9, S("1234567890"), 0, 0, S("abcdefghij"));
989    test(S("abcdefghij"), 9, S("1234567890"), 0, 1, S("abcdefghi1j"));
990    test(S("abcdefghij"), 9, S("1234567890"), 0, 5, S("abcdefghi12345j"));
991    test(S("abcdefghij"), 9, S("1234567890"), 0, 9, S("abcdefghi123456789j"));
992    test(S("abcdefghij"), 9, S("1234567890"), 0, 10, S("abcdefghi1234567890j"));
993    test(S("abcdefghij"), 9, S("1234567890"), 0, 11, S("abcdefghi1234567890j"));
994    test(S("abcdefghij"), 9, S("1234567890"), 1, 0, S("abcdefghij"));
995    test(S("abcdefghij"), 9, S("1234567890"), 1, 1, S("abcdefghi2j"));
996    test(S("abcdefghij"), 9, S("1234567890"), 1, 4, S("abcdefghi2345j"));
997    test(S("abcdefghij"), 9, S("1234567890"), 1, 8, S("abcdefghi23456789j"));
998}
999
1000template <class S>
1001void test17()
1002{
1003    test(S("abcdefghij"), 9, S("1234567890"), 1, 9, S("abcdefghi234567890j"));
1004    test(S("abcdefghij"), 9, S("1234567890"), 1, 10, S("abcdefghi234567890j"));
1005    test(S("abcdefghij"), 9, S("1234567890"), 5, 0, S("abcdefghij"));
1006    test(S("abcdefghij"), 9, S("1234567890"), 5, 1, S("abcdefghi6j"));
1007    test(S("abcdefghij"), 9, S("1234567890"), 5, 2, S("abcdefghi67j"));
1008    test(S("abcdefghij"), 9, S("1234567890"), 5, 4, S("abcdefghi6789j"));
1009    test(S("abcdefghij"), 9, S("1234567890"), 5, 5, S("abcdefghi67890j"));
1010    test(S("abcdefghij"), 9, S("1234567890"), 5, 6, S("abcdefghi67890j"));
1011    test(S("abcdefghij"), 9, S("1234567890"), 9, 0, S("abcdefghij"));
1012    test(S("abcdefghij"), 9, S("1234567890"), 9, 1, S("abcdefghi0j"));
1013    test(S("abcdefghij"), 9, S("1234567890"), 9, 2, S("abcdefghi0j"));
1014    test(S("abcdefghij"), 9, S("1234567890"), 10, 0, S("abcdefghij"));
1015    test(S("abcdefghij"), 9, S("1234567890"), 10, 1, S("abcdefghij"));
1016    test(S("abcdefghij"), 9, S("1234567890"), 11, 0, S("can't happen"));
1017    test(S("abcdefghij"), 9, S("12345678901234567890"), 0, 0, S("abcdefghij"));
1018    test(S("abcdefghij"), 9, S("12345678901234567890"), 0, 1, S("abcdefghi1j"));
1019    test(S("abcdefghij"), 9, S("12345678901234567890"), 0, 10, S("abcdefghi1234567890j"));
1020    test(S("abcdefghij"), 9, S("12345678901234567890"), 0, 19, S("abcdefghi1234567890123456789j"));
1021    test(S("abcdefghij"), 9, S("12345678901234567890"), 0, 20, S("abcdefghi12345678901234567890j"));
1022    test(S("abcdefghij"), 9, S("12345678901234567890"), 0, 21, S("abcdefghi12345678901234567890j"));
1023    test(S("abcdefghij"), 9, S("12345678901234567890"), 1, 0, S("abcdefghij"));
1024    test(S("abcdefghij"), 9, S("12345678901234567890"), 1, 1, S("abcdefghi2j"));
1025    test(S("abcdefghij"), 9, S("12345678901234567890"), 1, 9, S("abcdefghi234567890j"));
1026    test(S("abcdefghij"), 9, S("12345678901234567890"), 1, 18, S("abcdefghi234567890123456789j"));
1027    test(S("abcdefghij"), 9, S("12345678901234567890"), 1, 19, S("abcdefghi2345678901234567890j"));
1028    test(S("abcdefghij"), 9, S("12345678901234567890"), 1, 20, S("abcdefghi2345678901234567890j"));
1029    test(S("abcdefghij"), 9, S("12345678901234567890"), 10, 0, S("abcdefghij"));
1030    test(S("abcdefghij"), 9, S("12345678901234567890"), 10, 1, S("abcdefghi1j"));
1031    test(S("abcdefghij"), 9, S("12345678901234567890"), 10, 5, S("abcdefghi12345j"));
1032    test(S("abcdefghij"), 9, S("12345678901234567890"), 10, 9, S("abcdefghi123456789j"));
1033    test(S("abcdefghij"), 9, S("12345678901234567890"), 10, 10, S("abcdefghi1234567890j"));
1034    test(S("abcdefghij"), 9, S("12345678901234567890"), 10, 11, S("abcdefghi1234567890j"));
1035    test(S("abcdefghij"), 9, S("12345678901234567890"), 19, 0, S("abcdefghij"));
1036    test(S("abcdefghij"), 9, S("12345678901234567890"), 19, 1, S("abcdefghi0j"));
1037    test(S("abcdefghij"), 9, S("12345678901234567890"), 19, 2, S("abcdefghi0j"));
1038    test(S("abcdefghij"), 9, S("12345678901234567890"), 20, 0, S("abcdefghij"));
1039    test(S("abcdefghij"), 9, S("12345678901234567890"), 20, 1, S("abcdefghij"));
1040    test(S("abcdefghij"), 9, S("12345678901234567890"), 21, 0, S("can't happen"));
1041    test(S("abcdefghij"), 10, S(""), 0, 0, S("abcdefghij"));
1042    test(S("abcdefghij"), 10, S(""), 0, 1, S("abcdefghij"));
1043    test(S("abcdefghij"), 10, S(""), 1, 0, S("can't happen"));
1044    test(S("abcdefghij"), 10, S("12345"), 0, 0, S("abcdefghij"));
1045    test(S("abcdefghij"), 10, S("12345"), 0, 1, S("abcdefghij1"));
1046    test(S("abcdefghij"), 10, S("12345"), 0, 2, S("abcdefghij12"));
1047    test(S("abcdefghij"), 10, S("12345"), 0, 4, S("abcdefghij1234"));
1048    test(S("abcdefghij"), 10, S("12345"), 0, 5, S("abcdefghij12345"));
1049    test(S("abcdefghij"), 10, S("12345"), 0, 6, S("abcdefghij12345"));
1050    test(S("abcdefghij"), 10, S("12345"), 1, 0, S("abcdefghij"));
1051    test(S("abcdefghij"), 10, S("12345"), 1, 1, S("abcdefghij2"));
1052    test(S("abcdefghij"), 10, S("12345"), 1, 2, S("abcdefghij23"));
1053}
1054
1055template <class S>
1056void test18()
1057{
1058    test(S("abcdefghij"), 10, S("12345"), 1, 3, S("abcdefghij234"));
1059    test(S("abcdefghij"), 10, S("12345"), 1, 4, S("abcdefghij2345"));
1060    test(S("abcdefghij"), 10, S("12345"), 1, 5, S("abcdefghij2345"));
1061    test(S("abcdefghij"), 10, S("12345"), 2, 0, S("abcdefghij"));
1062    test(S("abcdefghij"), 10, S("12345"), 2, 1, S("abcdefghij3"));
1063    test(S("abcdefghij"), 10, S("12345"), 2, 2, S("abcdefghij34"));
1064    test(S("abcdefghij"), 10, S("12345"), 2, 3, S("abcdefghij345"));
1065    test(S("abcdefghij"), 10, S("12345"), 2, 4, S("abcdefghij345"));
1066    test(S("abcdefghij"), 10, S("12345"), 4, 0, S("abcdefghij"));
1067    test(S("abcdefghij"), 10, S("12345"), 4, 1, S("abcdefghij5"));
1068    test(S("abcdefghij"), 10, S("12345"), 4, 2, S("abcdefghij5"));
1069    test(S("abcdefghij"), 10, S("12345"), 5, 0, S("abcdefghij"));
1070    test(S("abcdefghij"), 10, S("12345"), 5, 1, S("abcdefghij"));
1071    test(S("abcdefghij"), 10, S("12345"), 6, 0, S("can't happen"));
1072    test(S("abcdefghij"), 10, S("1234567890"), 0, 0, S("abcdefghij"));
1073    test(S("abcdefghij"), 10, S("1234567890"), 0, 1, S("abcdefghij1"));
1074    test(S("abcdefghij"), 10, S("1234567890"), 0, 5, S("abcdefghij12345"));
1075    test(S("abcdefghij"), 10, S("1234567890"), 0, 9, S("abcdefghij123456789"));
1076    test(S("abcdefghij"), 10, S("1234567890"), 0, 10, S("abcdefghij1234567890"));
1077    test(S("abcdefghij"), 10, S("1234567890"), 0, 11, S("abcdefghij1234567890"));
1078    test(S("abcdefghij"), 10, S("1234567890"), 1, 0, S("abcdefghij"));
1079    test(S("abcdefghij"), 10, S("1234567890"), 1, 1, S("abcdefghij2"));
1080    test(S("abcdefghij"), 10, S("1234567890"), 1, 4, S("abcdefghij2345"));
1081    test(S("abcdefghij"), 10, S("1234567890"), 1, 8, S("abcdefghij23456789"));
1082    test(S("abcdefghij"), 10, S("1234567890"), 1, 9, S("abcdefghij234567890"));
1083    test(S("abcdefghij"), 10, S("1234567890"), 1, 10, S("abcdefghij234567890"));
1084    test(S("abcdefghij"), 10, S("1234567890"), 5, 0, S("abcdefghij"));
1085    test(S("abcdefghij"), 10, S("1234567890"), 5, 1, S("abcdefghij6"));
1086    test(S("abcdefghij"), 10, S("1234567890"), 5, 2, S("abcdefghij67"));
1087    test(S("abcdefghij"), 10, S("1234567890"), 5, 4, S("abcdefghij6789"));
1088    test(S("abcdefghij"), 10, S("1234567890"), 5, 5, S("abcdefghij67890"));
1089    test(S("abcdefghij"), 10, S("1234567890"), 5, 6, S("abcdefghij67890"));
1090    test(S("abcdefghij"), 10, S("1234567890"), 9, 0, S("abcdefghij"));
1091    test(S("abcdefghij"), 10, S("1234567890"), 9, 1, S("abcdefghij0"));
1092    test(S("abcdefghij"), 10, S("1234567890"), 9, 2, S("abcdefghij0"));
1093    test(S("abcdefghij"), 10, S("1234567890"), 10, 0, S("abcdefghij"));
1094    test(S("abcdefghij"), 10, S("1234567890"), 10, 1, S("abcdefghij"));
1095    test(S("abcdefghij"), 10, S("1234567890"), 11, 0, S("can't happen"));
1096    test(S("abcdefghij"), 10, S("12345678901234567890"), 0, 0, S("abcdefghij"));
1097    test(S("abcdefghij"), 10, S("12345678901234567890"), 0, 1, S("abcdefghij1"));
1098    test(S("abcdefghij"), 10, S("12345678901234567890"), 0, 10, S("abcdefghij1234567890"));
1099    test(S("abcdefghij"), 10, S("12345678901234567890"), 0, 19, S("abcdefghij1234567890123456789"));
1100    test(S("abcdefghij"), 10, S("12345678901234567890"), 0, 20, S("abcdefghij12345678901234567890"));
1101    test(S("abcdefghij"), 10, S("12345678901234567890"), 0, 21, S("abcdefghij12345678901234567890"));
1102    test(S("abcdefghij"), 10, S("12345678901234567890"), 1, 0, S("abcdefghij"));
1103    test(S("abcdefghij"), 10, S("12345678901234567890"), 1, 1, S("abcdefghij2"));
1104    test(S("abcdefghij"), 10, S("12345678901234567890"), 1, 9, S("abcdefghij234567890"));
1105    test(S("abcdefghij"), 10, S("12345678901234567890"), 1, 18, S("abcdefghij234567890123456789"));
1106    test(S("abcdefghij"), 10, S("12345678901234567890"), 1, 19, S("abcdefghij2345678901234567890"));
1107    test(S("abcdefghij"), 10, S("12345678901234567890"), 1, 20, S("abcdefghij2345678901234567890"));
1108}
1109
1110template <class S>
1111void test19()
1112{
1113    test(S("abcdefghij"), 10, S("12345678901234567890"), 10, 0, S("abcdefghij"));
1114    test(S("abcdefghij"), 10, S("12345678901234567890"), 10, 1, S("abcdefghij1"));
1115    test(S("abcdefghij"), 10, S("12345678901234567890"), 10, 5, S("abcdefghij12345"));
1116    test(S("abcdefghij"), 10, S("12345678901234567890"), 10, 9, S("abcdefghij123456789"));
1117    test(S("abcdefghij"), 10, S("12345678901234567890"), 10, 10, S("abcdefghij1234567890"));
1118    test(S("abcdefghij"), 10, S("12345678901234567890"), 10, 11, S("abcdefghij1234567890"));
1119    test(S("abcdefghij"), 10, S("12345678901234567890"), 19, 0, S("abcdefghij"));
1120    test(S("abcdefghij"), 10, S("12345678901234567890"), 19, 1, S("abcdefghij0"));
1121    test(S("abcdefghij"), 10, S("12345678901234567890"), 19, 2, S("abcdefghij0"));
1122    test(S("abcdefghij"), 10, S("12345678901234567890"), 20, 0, S("abcdefghij"));
1123    test(S("abcdefghij"), 10, S("12345678901234567890"), 20, 1, S("abcdefghij"));
1124    test(S("abcdefghij"), 10, S("12345678901234567890"), 21, 0, S("can't happen"));
1125    test(S("abcdefghij"), 11, S(""), 0, 0, S("can't happen"));
1126    test(S("abcdefghij"), 11, S(""), 0, 1, S("can't happen"));
1127    test(S("abcdefghij"), 11, S(""), 1, 0, S("can't happen"));
1128    test(S("abcdefghij"), 11, S("12345"), 0, 0, S("can't happen"));
1129    test(S("abcdefghij"), 11, S("12345"), 0, 1, S("can't happen"));
1130    test(S("abcdefghij"), 11, S("12345"), 0, 2, S("can't happen"));
1131    test(S("abcdefghij"), 11, S("12345"), 0, 4, S("can't happen"));
1132    test(S("abcdefghij"), 11, S("12345"), 0, 5, S("can't happen"));
1133    test(S("abcdefghij"), 11, S("12345"), 0, 6, S("can't happen"));
1134    test(S("abcdefghij"), 11, S("12345"), 1, 0, S("can't happen"));
1135    test(S("abcdefghij"), 11, S("12345"), 1, 1, S("can't happen"));
1136    test(S("abcdefghij"), 11, S("12345"), 1, 2, S("can't happen"));
1137    test(S("abcdefghij"), 11, S("12345"), 1, 3, S("can't happen"));
1138    test(S("abcdefghij"), 11, S("12345"), 1, 4, S("can't happen"));
1139    test(S("abcdefghij"), 11, S("12345"), 1, 5, S("can't happen"));
1140    test(S("abcdefghij"), 11, S("12345"), 2, 0, S("can't happen"));
1141    test(S("abcdefghij"), 11, S("12345"), 2, 1, S("can't happen"));
1142    test(S("abcdefghij"), 11, S("12345"), 2, 2, S("can't happen"));
1143    test(S("abcdefghij"), 11, S("12345"), 2, 3, S("can't happen"));
1144    test(S("abcdefghij"), 11, S("12345"), 2, 4, S("can't happen"));
1145    test(S("abcdefghij"), 11, S("12345"), 4, 0, S("can't happen"));
1146    test(S("abcdefghij"), 11, S("12345"), 4, 1, S("can't happen"));
1147    test(S("abcdefghij"), 11, S("12345"), 4, 2, S("can't happen"));
1148    test(S("abcdefghij"), 11, S("12345"), 5, 0, S("can't happen"));
1149    test(S("abcdefghij"), 11, S("12345"), 5, 1, S("can't happen"));
1150    test(S("abcdefghij"), 11, S("12345"), 6, 0, S("can't happen"));
1151    test(S("abcdefghij"), 11, S("1234567890"), 0, 0, S("can't happen"));
1152    test(S("abcdefghij"), 11, S("1234567890"), 0, 1, S("can't happen"));
1153    test(S("abcdefghij"), 11, S("1234567890"), 0, 5, S("can't happen"));
1154    test(S("abcdefghij"), 11, S("1234567890"), 0, 9, S("can't happen"));
1155    test(S("abcdefghij"), 11, S("1234567890"), 0, 10, S("can't happen"));
1156    test(S("abcdefghij"), 11, S("1234567890"), 0, 11, S("can't happen"));
1157    test(S("abcdefghij"), 11, S("1234567890"), 1, 0, S("can't happen"));
1158    test(S("abcdefghij"), 11, S("1234567890"), 1, 1, S("can't happen"));
1159    test(S("abcdefghij"), 11, S("1234567890"), 1, 4, S("can't happen"));
1160    test(S("abcdefghij"), 11, S("1234567890"), 1, 8, S("can't happen"));
1161    test(S("abcdefghij"), 11, S("1234567890"), 1, 9, S("can't happen"));
1162    test(S("abcdefghij"), 11, S("1234567890"), 1, 10, S("can't happen"));
1163}
1164
1165template <class S>
1166void test20()
1167{
1168    test(S("abcdefghij"), 11, S("1234567890"), 5, 0, S("can't happen"));
1169    test(S("abcdefghij"), 11, S("1234567890"), 5, 1, S("can't happen"));
1170    test(S("abcdefghij"), 11, S("1234567890"), 5, 2, S("can't happen"));
1171    test(S("abcdefghij"), 11, S("1234567890"), 5, 4, S("can't happen"));
1172    test(S("abcdefghij"), 11, S("1234567890"), 5, 5, S("can't happen"));
1173    test(S("abcdefghij"), 11, S("1234567890"), 5, 6, S("can't happen"));
1174    test(S("abcdefghij"), 11, S("1234567890"), 9, 0, S("can't happen"));
1175    test(S("abcdefghij"), 11, S("1234567890"), 9, 1, S("can't happen"));
1176    test(S("abcdefghij"), 11, S("1234567890"), 9, 2, S("can't happen"));
1177    test(S("abcdefghij"), 11, S("1234567890"), 10, 0, S("can't happen"));
1178    test(S("abcdefghij"), 11, S("1234567890"), 10, 1, S("can't happen"));
1179    test(S("abcdefghij"), 11, S("1234567890"), 11, 0, S("can't happen"));
1180    test(S("abcdefghij"), 11, S("12345678901234567890"), 0, 0, S("can't happen"));
1181    test(S("abcdefghij"), 11, S("12345678901234567890"), 0, 1, S("can't happen"));
1182    test(S("abcdefghij"), 11, S("12345678901234567890"), 0, 10, S("can't happen"));
1183    test(S("abcdefghij"), 11, S("12345678901234567890"), 0, 19, S("can't happen"));
1184    test(S("abcdefghij"), 11, S("12345678901234567890"), 0, 20, S("can't happen"));
1185    test(S("abcdefghij"), 11, S("12345678901234567890"), 0, 21, S("can't happen"));
1186    test(S("abcdefghij"), 11, S("12345678901234567890"), 1, 0, S("can't happen"));
1187    test(S("abcdefghij"), 11, S("12345678901234567890"), 1, 1, S("can't happen"));
1188    test(S("abcdefghij"), 11, S("12345678901234567890"), 1, 9, S("can't happen"));
1189    test(S("abcdefghij"), 11, S("12345678901234567890"), 1, 18, S("can't happen"));
1190    test(S("abcdefghij"), 11, S("12345678901234567890"), 1, 19, S("can't happen"));
1191    test(S("abcdefghij"), 11, S("12345678901234567890"), 1, 20, S("can't happen"));
1192    test(S("abcdefghij"), 11, S("12345678901234567890"), 10, 0, S("can't happen"));
1193    test(S("abcdefghij"), 11, S("12345678901234567890"), 10, 1, S("can't happen"));
1194    test(S("abcdefghij"), 11, S("12345678901234567890"), 10, 5, S("can't happen"));
1195    test(S("abcdefghij"), 11, S("12345678901234567890"), 10, 9, S("can't happen"));
1196    test(S("abcdefghij"), 11, S("12345678901234567890"), 10, 10, S("can't happen"));
1197    test(S("abcdefghij"), 11, S("12345678901234567890"), 10, 11, S("can't happen"));
1198    test(S("abcdefghij"), 11, S("12345678901234567890"), 19, 0, S("can't happen"));
1199    test(S("abcdefghij"), 11, S("12345678901234567890"), 19, 1, S("can't happen"));
1200    test(S("abcdefghij"), 11, S("12345678901234567890"), 19, 2, S("can't happen"));
1201    test(S("abcdefghij"), 11, S("12345678901234567890"), 20, 0, S("can't happen"));
1202    test(S("abcdefghij"), 11, S("12345678901234567890"), 20, 1, S("can't happen"));
1203    test(S("abcdefghij"), 11, S("12345678901234567890"), 21, 0, S("can't happen"));
1204    test(S("abcdefghijklmnopqrst"), 0, S(""), 0, 0, S("abcdefghijklmnopqrst"));
1205    test(S("abcdefghijklmnopqrst"), 0, S(""), 0, 1, S("abcdefghijklmnopqrst"));
1206    test(S("abcdefghijklmnopqrst"), 0, S(""), 1, 0, S("can't happen"));
1207    test(S("abcdefghijklmnopqrst"), 0, S("12345"), 0, 0, S("abcdefghijklmnopqrst"));
1208    test(S("abcdefghijklmnopqrst"), 0, S("12345"), 0, 1, S("1abcdefghijklmnopqrst"));
1209    test(S("abcdefghijklmnopqrst"), 0, S("12345"), 0, 2, S("12abcdefghijklmnopqrst"));
1210    test(S("abcdefghijklmnopqrst"), 0, S("12345"), 0, 4, S("1234abcdefghijklmnopqrst"));
1211    test(S("abcdefghijklmnopqrst"), 0, S("12345"), 0, 5, S("12345abcdefghijklmnopqrst"));
1212    test(S("abcdefghijklmnopqrst"), 0, S("12345"), 0, 6, S("12345abcdefghijklmnopqrst"));
1213    test(S("abcdefghijklmnopqrst"), 0, S("12345"), 1, 0, S("abcdefghijklmnopqrst"));
1214    test(S("abcdefghijklmnopqrst"), 0, S("12345"), 1, 1, S("2abcdefghijklmnopqrst"));
1215    test(S("abcdefghijklmnopqrst"), 0, S("12345"), 1, 2, S("23abcdefghijklmnopqrst"));
1216    test(S("abcdefghijklmnopqrst"), 0, S("12345"), 1, 3, S("234abcdefghijklmnopqrst"));
1217    test(S("abcdefghijklmnopqrst"), 0, S("12345"), 1, 4, S("2345abcdefghijklmnopqrst"));
1218}
1219
1220template <class S>
1221void test21()
1222{
1223    test(S("abcdefghijklmnopqrst"), 0, S("12345"), 1, 5, S("2345abcdefghijklmnopqrst"));
1224    test(S("abcdefghijklmnopqrst"), 0, S("12345"), 2, 0, S("abcdefghijklmnopqrst"));
1225    test(S("abcdefghijklmnopqrst"), 0, S("12345"), 2, 1, S("3abcdefghijklmnopqrst"));
1226    test(S("abcdefghijklmnopqrst"), 0, S("12345"), 2, 2, S("34abcdefghijklmnopqrst"));
1227    test(S("abcdefghijklmnopqrst"), 0, S("12345"), 2, 3, S("345abcdefghijklmnopqrst"));
1228    test(S("abcdefghijklmnopqrst"), 0, S("12345"), 2, 4, S("345abcdefghijklmnopqrst"));
1229    test(S("abcdefghijklmnopqrst"), 0, S("12345"), 4, 0, S("abcdefghijklmnopqrst"));
1230    test(S("abcdefghijklmnopqrst"), 0, S("12345"), 4, 1, S("5abcdefghijklmnopqrst"));
1231    test(S("abcdefghijklmnopqrst"), 0, S("12345"), 4, 2, S("5abcdefghijklmnopqrst"));
1232    test(S("abcdefghijklmnopqrst"), 0, S("12345"), 5, 0, S("abcdefghijklmnopqrst"));
1233    test(S("abcdefghijklmnopqrst"), 0, S("12345"), 5, 1, S("abcdefghijklmnopqrst"));
1234    test(S("abcdefghijklmnopqrst"), 0, S("12345"), 6, 0, S("can't happen"));
1235    test(S("abcdefghijklmnopqrst"), 0, S("1234567890"), 0, 0, S("abcdefghijklmnopqrst"));
1236    test(S("abcdefghijklmnopqrst"), 0, S("1234567890"), 0, 1, S("1abcdefghijklmnopqrst"));
1237    test(S("abcdefghijklmnopqrst"), 0, S("1234567890"), 0, 5, S("12345abcdefghijklmnopqrst"));
1238    test(S("abcdefghijklmnopqrst"), 0, S("1234567890"), 0, 9, S("123456789abcdefghijklmnopqrst"));
1239    test(S("abcdefghijklmnopqrst"), 0, S("1234567890"), 0, 10, S("1234567890abcdefghijklmnopqrst"));
1240    test(S("abcdefghijklmnopqrst"), 0, S("1234567890"), 0, 11, S("1234567890abcdefghijklmnopqrst"));
1241    test(S("abcdefghijklmnopqrst"), 0, S("1234567890"), 1, 0, S("abcdefghijklmnopqrst"));
1242    test(S("abcdefghijklmnopqrst"), 0, S("1234567890"), 1, 1, S("2abcdefghijklmnopqrst"));
1243    test(S("abcdefghijklmnopqrst"), 0, S("1234567890"), 1, 4, S("2345abcdefghijklmnopqrst"));
1244    test(S("abcdefghijklmnopqrst"), 0, S("1234567890"), 1, 8, S("23456789abcdefghijklmnopqrst"));
1245    test(S("abcdefghijklmnopqrst"), 0, S("1234567890"), 1, 9, S("234567890abcdefghijklmnopqrst"));
1246    test(S("abcdefghijklmnopqrst"), 0, S("1234567890"), 1, 10, S("234567890abcdefghijklmnopqrst"));
1247    test(S("abcdefghijklmnopqrst"), 0, S("1234567890"), 5, 0, S("abcdefghijklmnopqrst"));
1248    test(S("abcdefghijklmnopqrst"), 0, S("1234567890"), 5, 1, S("6abcdefghijklmnopqrst"));
1249    test(S("abcdefghijklmnopqrst"), 0, S("1234567890"), 5, 2, S("67abcdefghijklmnopqrst"));
1250    test(S("abcdefghijklmnopqrst"), 0, S("1234567890"), 5, 4, S("6789abcdefghijklmnopqrst"));
1251    test(S("abcdefghijklmnopqrst"), 0, S("1234567890"), 5, 5, S("67890abcdefghijklmnopqrst"));
1252    test(S("abcdefghijklmnopqrst"), 0, S("1234567890"), 5, 6, S("67890abcdefghijklmnopqrst"));
1253    test(S("abcdefghijklmnopqrst"), 0, S("1234567890"), 9, 0, S("abcdefghijklmnopqrst"));
1254    test(S("abcdefghijklmnopqrst"), 0, S("1234567890"), 9, 1, S("0abcdefghijklmnopqrst"));
1255    test(S("abcdefghijklmnopqrst"), 0, S("1234567890"), 9, 2, S("0abcdefghijklmnopqrst"));
1256    test(S("abcdefghijklmnopqrst"), 0, S("1234567890"), 10, 0, S("abcdefghijklmnopqrst"));
1257    test(S("abcdefghijklmnopqrst"), 0, S("1234567890"), 10, 1, S("abcdefghijklmnopqrst"));
1258    test(S("abcdefghijklmnopqrst"), 0, S("1234567890"), 11, 0, S("can't happen"));
1259    test(S("abcdefghijklmnopqrst"), 0, S("12345678901234567890"), 0, 0, S("abcdefghijklmnopqrst"));
1260    test(S("abcdefghijklmnopqrst"), 0, S("12345678901234567890"), 0, 1, S("1abcdefghijklmnopqrst"));
1261    test(S("abcdefghijklmnopqrst"), 0, S("12345678901234567890"), 0, 10, S("1234567890abcdefghijklmnopqrst"));
1262    test(S("abcdefghijklmnopqrst"), 0, S("12345678901234567890"), 0, 19, S("1234567890123456789abcdefghijklmnopqrst"));
1263    test(S("abcdefghijklmnopqrst"), 0, S("12345678901234567890"), 0, 20, S("12345678901234567890abcdefghijklmnopqrst"));
1264    test(S("abcdefghijklmnopqrst"), 0, S("12345678901234567890"), 0, 21, S("12345678901234567890abcdefghijklmnopqrst"));
1265    test(S("abcdefghijklmnopqrst"), 0, S("12345678901234567890"), 1, 0, S("abcdefghijklmnopqrst"));
1266    test(S("abcdefghijklmnopqrst"), 0, S("12345678901234567890"), 1, 1, S("2abcdefghijklmnopqrst"));
1267    test(S("abcdefghijklmnopqrst"), 0, S("12345678901234567890"), 1, 9, S("234567890abcdefghijklmnopqrst"));
1268    test(S("abcdefghijklmnopqrst"), 0, S("12345678901234567890"), 1, 18, S("234567890123456789abcdefghijklmnopqrst"));
1269    test(S("abcdefghijklmnopqrst"), 0, S("12345678901234567890"), 1, 19, S("2345678901234567890abcdefghijklmnopqrst"));
1270    test(S("abcdefghijklmnopqrst"), 0, S("12345678901234567890"), 1, 20, S("2345678901234567890abcdefghijklmnopqrst"));
1271    test(S("abcdefghijklmnopqrst"), 0, S("12345678901234567890"), 10, 0, S("abcdefghijklmnopqrst"));
1272    test(S("abcdefghijklmnopqrst"), 0, S("12345678901234567890"), 10, 1, S("1abcdefghijklmnopqrst"));
1273}
1274
1275template <class S>
1276void test22()
1277{
1278    test(S("abcdefghijklmnopqrst"), 0, S("12345678901234567890"), 10, 5, S("12345abcdefghijklmnopqrst"));
1279    test(S("abcdefghijklmnopqrst"), 0, S("12345678901234567890"), 10, 9, S("123456789abcdefghijklmnopqrst"));
1280    test(S("abcdefghijklmnopqrst"), 0, S("12345678901234567890"), 10, 10, S("1234567890abcdefghijklmnopqrst"));
1281    test(S("abcdefghijklmnopqrst"), 0, S("12345678901234567890"), 10, 11, S("1234567890abcdefghijklmnopqrst"));
1282    test(S("abcdefghijklmnopqrst"), 0, S("12345678901234567890"), 19, 0, S("abcdefghijklmnopqrst"));
1283    test(S("abcdefghijklmnopqrst"), 0, S("12345678901234567890"), 19, 1, S("0abcdefghijklmnopqrst"));
1284    test(S("abcdefghijklmnopqrst"), 0, S("12345678901234567890"), 19, 2, S("0abcdefghijklmnopqrst"));
1285    test(S("abcdefghijklmnopqrst"), 0, S("12345678901234567890"), 20, 0, S("abcdefghijklmnopqrst"));
1286    test(S("abcdefghijklmnopqrst"), 0, S("12345678901234567890"), 20, 1, S("abcdefghijklmnopqrst"));
1287    test(S("abcdefghijklmnopqrst"), 0, S("12345678901234567890"), 21, 0, S("can't happen"));
1288    test(S("abcdefghijklmnopqrst"), 1, S(""), 0, 0, S("abcdefghijklmnopqrst"));
1289    test(S("abcdefghijklmnopqrst"), 1, S(""), 0, 1, S("abcdefghijklmnopqrst"));
1290    test(S("abcdefghijklmnopqrst"), 1, S(""), 1, 0, S("can't happen"));
1291    test(S("abcdefghijklmnopqrst"), 1, S("12345"), 0, 0, S("abcdefghijklmnopqrst"));
1292    test(S("abcdefghijklmnopqrst"), 1, S("12345"), 0, 1, S("a1bcdefghijklmnopqrst"));
1293    test(S("abcdefghijklmnopqrst"), 1, S("12345"), 0, 2, S("a12bcdefghijklmnopqrst"));
1294    test(S("abcdefghijklmnopqrst"), 1, S("12345"), 0, 4, S("a1234bcdefghijklmnopqrst"));
1295    test(S("abcdefghijklmnopqrst"), 1, S("12345"), 0, 5, S("a12345bcdefghijklmnopqrst"));
1296    test(S("abcdefghijklmnopqrst"), 1, S("12345"), 0, 6, S("a12345bcdefghijklmnopqrst"));
1297    test(S("abcdefghijklmnopqrst"), 1, S("12345"), 1, 0, S("abcdefghijklmnopqrst"));
1298    test(S("abcdefghijklmnopqrst"), 1, S("12345"), 1, 1, S("a2bcdefghijklmnopqrst"));
1299    test(S("abcdefghijklmnopqrst"), 1, S("12345"), 1, 2, S("a23bcdefghijklmnopqrst"));
1300    test(S("abcdefghijklmnopqrst"), 1, S("12345"), 1, 3, S("a234bcdefghijklmnopqrst"));
1301    test(S("abcdefghijklmnopqrst"), 1, S("12345"), 1, 4, S("a2345bcdefghijklmnopqrst"));
1302    test(S("abcdefghijklmnopqrst"), 1, S("12345"), 1, 5, S("a2345bcdefghijklmnopqrst"));
1303    test(S("abcdefghijklmnopqrst"), 1, S("12345"), 2, 0, S("abcdefghijklmnopqrst"));
1304    test(S("abcdefghijklmnopqrst"), 1, S("12345"), 2, 1, S("a3bcdefghijklmnopqrst"));
1305    test(S("abcdefghijklmnopqrst"), 1, S("12345"), 2, 2, S("a34bcdefghijklmnopqrst"));
1306    test(S("abcdefghijklmnopqrst"), 1, S("12345"), 2, 3, S("a345bcdefghijklmnopqrst"));
1307    test(S("abcdefghijklmnopqrst"), 1, S("12345"), 2, 4, S("a345bcdefghijklmnopqrst"));
1308    test(S("abcdefghijklmnopqrst"), 1, S("12345"), 4, 0, S("abcdefghijklmnopqrst"));
1309    test(S("abcdefghijklmnopqrst"), 1, S("12345"), 4, 1, S("a5bcdefghijklmnopqrst"));
1310    test(S("abcdefghijklmnopqrst"), 1, S("12345"), 4, 2, S("a5bcdefghijklmnopqrst"));
1311    test(S("abcdefghijklmnopqrst"), 1, S("12345"), 5, 0, S("abcdefghijklmnopqrst"));
1312    test(S("abcdefghijklmnopqrst"), 1, S("12345"), 5, 1, S("abcdefghijklmnopqrst"));
1313    test(S("abcdefghijklmnopqrst"), 1, S("12345"), 6, 0, S("can't happen"));
1314    test(S("abcdefghijklmnopqrst"), 1, S("1234567890"), 0, 0, S("abcdefghijklmnopqrst"));
1315    test(S("abcdefghijklmnopqrst"), 1, S("1234567890"), 0, 1, S("a1bcdefghijklmnopqrst"));
1316    test(S("abcdefghijklmnopqrst"), 1, S("1234567890"), 0, 5, S("a12345bcdefghijklmnopqrst"));
1317    test(S("abcdefghijklmnopqrst"), 1, S("1234567890"), 0, 9, S("a123456789bcdefghijklmnopqrst"));
1318    test(S("abcdefghijklmnopqrst"), 1, S("1234567890"), 0, 10, S("a1234567890bcdefghijklmnopqrst"));
1319    test(S("abcdefghijklmnopqrst"), 1, S("1234567890"), 0, 11, S("a1234567890bcdefghijklmnopqrst"));
1320    test(S("abcdefghijklmnopqrst"), 1, S("1234567890"), 1, 0, S("abcdefghijklmnopqrst"));
1321    test(S("abcdefghijklmnopqrst"), 1, S("1234567890"), 1, 1, S("a2bcdefghijklmnopqrst"));
1322    test(S("abcdefghijklmnopqrst"), 1, S("1234567890"), 1, 4, S("a2345bcdefghijklmnopqrst"));
1323    test(S("abcdefghijklmnopqrst"), 1, S("1234567890"), 1, 8, S("a23456789bcdefghijklmnopqrst"));
1324    test(S("abcdefghijklmnopqrst"), 1, S("1234567890"), 1, 9, S("a234567890bcdefghijklmnopqrst"));
1325    test(S("abcdefghijklmnopqrst"), 1, S("1234567890"), 1, 10, S("a234567890bcdefghijklmnopqrst"));
1326    test(S("abcdefghijklmnopqrst"), 1, S("1234567890"), 5, 0, S("abcdefghijklmnopqrst"));
1327    test(S("abcdefghijklmnopqrst"), 1, S("1234567890"), 5, 1, S("a6bcdefghijklmnopqrst"));
1328}
1329
1330template <class S>
1331void test23()
1332{
1333    test(S("abcdefghijklmnopqrst"), 1, S("1234567890"), 5, 2, S("a67bcdefghijklmnopqrst"));
1334    test(S("abcdefghijklmnopqrst"), 1, S("1234567890"), 5, 4, S("a6789bcdefghijklmnopqrst"));
1335    test(S("abcdefghijklmnopqrst"), 1, S("1234567890"), 5, 5, S("a67890bcdefghijklmnopqrst"));
1336    test(S("abcdefghijklmnopqrst"), 1, S("1234567890"), 5, 6, S("a67890bcdefghijklmnopqrst"));
1337    test(S("abcdefghijklmnopqrst"), 1, S("1234567890"), 9, 0, S("abcdefghijklmnopqrst"));
1338    test(S("abcdefghijklmnopqrst"), 1, S("1234567890"), 9, 1, S("a0bcdefghijklmnopqrst"));
1339    test(S("abcdefghijklmnopqrst"), 1, S("1234567890"), 9, 2, S("a0bcdefghijklmnopqrst"));
1340    test(S("abcdefghijklmnopqrst"), 1, S("1234567890"), 10, 0, S("abcdefghijklmnopqrst"));
1341    test(S("abcdefghijklmnopqrst"), 1, S("1234567890"), 10, 1, S("abcdefghijklmnopqrst"));
1342    test(S("abcdefghijklmnopqrst"), 1, S("1234567890"), 11, 0, S("can't happen"));
1343    test(S("abcdefghijklmnopqrst"), 1, S("12345678901234567890"), 0, 0, S("abcdefghijklmnopqrst"));
1344    test(S("abcdefghijklmnopqrst"), 1, S("12345678901234567890"), 0, 1, S("a1bcdefghijklmnopqrst"));
1345    test(S("abcdefghijklmnopqrst"), 1, S("12345678901234567890"), 0, 10, S("a1234567890bcdefghijklmnopqrst"));
1346    test(S("abcdefghijklmnopqrst"), 1, S("12345678901234567890"), 0, 19, S("a1234567890123456789bcdefghijklmnopqrst"));
1347    test(S("abcdefghijklmnopqrst"), 1, S("12345678901234567890"), 0, 20, S("a12345678901234567890bcdefghijklmnopqrst"));
1348    test(S("abcdefghijklmnopqrst"), 1, S("12345678901234567890"), 0, 21, S("a12345678901234567890bcdefghijklmnopqrst"));
1349    test(S("abcdefghijklmnopqrst"), 1, S("12345678901234567890"), 1, 0, S("abcdefghijklmnopqrst"));
1350    test(S("abcdefghijklmnopqrst"), 1, S("12345678901234567890"), 1, 1, S("a2bcdefghijklmnopqrst"));
1351    test(S("abcdefghijklmnopqrst"), 1, S("12345678901234567890"), 1, 9, S("a234567890bcdefghijklmnopqrst"));
1352    test(S("abcdefghijklmnopqrst"), 1, S("12345678901234567890"), 1, 18, S("a234567890123456789bcdefghijklmnopqrst"));
1353    test(S("abcdefghijklmnopqrst"), 1, S("12345678901234567890"), 1, 19, S("a2345678901234567890bcdefghijklmnopqrst"));
1354    test(S("abcdefghijklmnopqrst"), 1, S("12345678901234567890"), 1, 20, S("a2345678901234567890bcdefghijklmnopqrst"));
1355    test(S("abcdefghijklmnopqrst"), 1, S("12345678901234567890"), 10, 0, S("abcdefghijklmnopqrst"));
1356    test(S("abcdefghijklmnopqrst"), 1, S("12345678901234567890"), 10, 1, S("a1bcdefghijklmnopqrst"));
1357    test(S("abcdefghijklmnopqrst"), 1, S("12345678901234567890"), 10, 5, S("a12345bcdefghijklmnopqrst"));
1358    test(S("abcdefghijklmnopqrst"), 1, S("12345678901234567890"), 10, 9, S("a123456789bcdefghijklmnopqrst"));
1359    test(S("abcdefghijklmnopqrst"), 1, S("12345678901234567890"), 10, 10, S("a1234567890bcdefghijklmnopqrst"));
1360    test(S("abcdefghijklmnopqrst"), 1, S("12345678901234567890"), 10, 11, S("a1234567890bcdefghijklmnopqrst"));
1361    test(S("abcdefghijklmnopqrst"), 1, S("12345678901234567890"), 19, 0, S("abcdefghijklmnopqrst"));
1362    test(S("abcdefghijklmnopqrst"), 1, S("12345678901234567890"), 19, 1, S("a0bcdefghijklmnopqrst"));
1363    test(S("abcdefghijklmnopqrst"), 1, S("12345678901234567890"), 19, 2, S("a0bcdefghijklmnopqrst"));
1364    test(S("abcdefghijklmnopqrst"), 1, S("12345678901234567890"), 20, 0, S("abcdefghijklmnopqrst"));
1365    test(S("abcdefghijklmnopqrst"), 1, S("12345678901234567890"), 20, 1, S("abcdefghijklmnopqrst"));
1366    test(S("abcdefghijklmnopqrst"), 1, S("12345678901234567890"), 21, 0, S("can't happen"));
1367    test(S("abcdefghijklmnopqrst"), 10, S(""), 0, 0, S("abcdefghijklmnopqrst"));
1368    test(S("abcdefghijklmnopqrst"), 10, S(""), 0, 1, S("abcdefghijklmnopqrst"));
1369    test(S("abcdefghijklmnopqrst"), 10, S(""), 1, 0, S("can't happen"));
1370    test(S("abcdefghijklmnopqrst"), 10, S("12345"), 0, 0, S("abcdefghijklmnopqrst"));
1371    test(S("abcdefghijklmnopqrst"), 10, S("12345"), 0, 1, S("abcdefghij1klmnopqrst"));
1372    test(S("abcdefghijklmnopqrst"), 10, S("12345"), 0, 2, S("abcdefghij12klmnopqrst"));
1373    test(S("abcdefghijklmnopqrst"), 10, S("12345"), 0, 4, S("abcdefghij1234klmnopqrst"));
1374    test(S("abcdefghijklmnopqrst"), 10, S("12345"), 0, 5, S("abcdefghij12345klmnopqrst"));
1375    test(S("abcdefghijklmnopqrst"), 10, S("12345"), 0, 6, S("abcdefghij12345klmnopqrst"));
1376    test(S("abcdefghijklmnopqrst"), 10, S("12345"), 1, 0, S("abcdefghijklmnopqrst"));
1377    test(S("abcdefghijklmnopqrst"), 10, S("12345"), 1, 1, S("abcdefghij2klmnopqrst"));
1378    test(S("abcdefghijklmnopqrst"), 10, S("12345"), 1, 2, S("abcdefghij23klmnopqrst"));
1379    test(S("abcdefghijklmnopqrst"), 10, S("12345"), 1, 3, S("abcdefghij234klmnopqrst"));
1380    test(S("abcdefghijklmnopqrst"), 10, S("12345"), 1, 4, S("abcdefghij2345klmnopqrst"));
1381    test(S("abcdefghijklmnopqrst"), 10, S("12345"), 1, 5, S("abcdefghij2345klmnopqrst"));
1382    test(S("abcdefghijklmnopqrst"), 10, S("12345"), 2, 0, S("abcdefghijklmnopqrst"));
1383}
1384
1385template <class S>
1386void test24()
1387{
1388    test(S("abcdefghijklmnopqrst"), 10, S("12345"), 2, 1, S("abcdefghij3klmnopqrst"));
1389    test(S("abcdefghijklmnopqrst"), 10, S("12345"), 2, 2, S("abcdefghij34klmnopqrst"));
1390    test(S("abcdefghijklmnopqrst"), 10, S("12345"), 2, 3, S("abcdefghij345klmnopqrst"));
1391    test(S("abcdefghijklmnopqrst"), 10, S("12345"), 2, 4, S("abcdefghij345klmnopqrst"));
1392    test(S("abcdefghijklmnopqrst"), 10, S("12345"), 4, 0, S("abcdefghijklmnopqrst"));
1393    test(S("abcdefghijklmnopqrst"), 10, S("12345"), 4, 1, S("abcdefghij5klmnopqrst"));
1394    test(S("abcdefghijklmnopqrst"), 10, S("12345"), 4, 2, S("abcdefghij5klmnopqrst"));
1395    test(S("abcdefghijklmnopqrst"), 10, S("12345"), 5, 0, S("abcdefghijklmnopqrst"));
1396    test(S("abcdefghijklmnopqrst"), 10, S("12345"), 5, 1, S("abcdefghijklmnopqrst"));
1397    test(S("abcdefghijklmnopqrst"), 10, S("12345"), 6, 0, S("can't happen"));
1398    test(S("abcdefghijklmnopqrst"), 10, S("1234567890"), 0, 0, S("abcdefghijklmnopqrst"));
1399    test(S("abcdefghijklmnopqrst"), 10, S("1234567890"), 0, 1, S("abcdefghij1klmnopqrst"));
1400    test(S("abcdefghijklmnopqrst"), 10, S("1234567890"), 0, 5, S("abcdefghij12345klmnopqrst"));
1401    test(S("abcdefghijklmnopqrst"), 10, S("1234567890"), 0, 9, S("abcdefghij123456789klmnopqrst"));
1402    test(S("abcdefghijklmnopqrst"), 10, S("1234567890"), 0, 10, S("abcdefghij1234567890klmnopqrst"));
1403    test(S("abcdefghijklmnopqrst"), 10, S("1234567890"), 0, 11, S("abcdefghij1234567890klmnopqrst"));
1404    test(S("abcdefghijklmnopqrst"), 10, S("1234567890"), 1, 0, S("abcdefghijklmnopqrst"));
1405    test(S("abcdefghijklmnopqrst"), 10, S("1234567890"), 1, 1, S("abcdefghij2klmnopqrst"));
1406    test(S("abcdefghijklmnopqrst"), 10, S("1234567890"), 1, 4, S("abcdefghij2345klmnopqrst"));
1407    test(S("abcdefghijklmnopqrst"), 10, S("1234567890"), 1, 8, S("abcdefghij23456789klmnopqrst"));
1408    test(S("abcdefghijklmnopqrst"), 10, S("1234567890"), 1, 9, S("abcdefghij234567890klmnopqrst"));
1409    test(S("abcdefghijklmnopqrst"), 10, S("1234567890"), 1, 10, S("abcdefghij234567890klmnopqrst"));
1410    test(S("abcdefghijklmnopqrst"), 10, S("1234567890"), 5, 0, S("abcdefghijklmnopqrst"));
1411    test(S("abcdefghijklmnopqrst"), 10, S("1234567890"), 5, 1, S("abcdefghij6klmnopqrst"));
1412    test(S("abcdefghijklmnopqrst"), 10, S("1234567890"), 5, 2, S("abcdefghij67klmnopqrst"));
1413    test(S("abcdefghijklmnopqrst"), 10, S("1234567890"), 5, 4, S("abcdefghij6789klmnopqrst"));
1414    test(S("abcdefghijklmnopqrst"), 10, S("1234567890"), 5, 5, S("abcdefghij67890klmnopqrst"));
1415    test(S("abcdefghijklmnopqrst"), 10, S("1234567890"), 5, 6, S("abcdefghij67890klmnopqrst"));
1416    test(S("abcdefghijklmnopqrst"), 10, S("1234567890"), 9, 0, S("abcdefghijklmnopqrst"));
1417    test(S("abcdefghijklmnopqrst"), 10, S("1234567890"), 9, 1, S("abcdefghij0klmnopqrst"));
1418    test(S("abcdefghijklmnopqrst"), 10, S("1234567890"), 9, 2, S("abcdefghij0klmnopqrst"));
1419    test(S("abcdefghijklmnopqrst"), 10, S("1234567890"), 10, 0, S("abcdefghijklmnopqrst"));
1420    test(S("abcdefghijklmnopqrst"), 10, S("1234567890"), 10, 1, S("abcdefghijklmnopqrst"));
1421    test(S("abcdefghijklmnopqrst"), 10, S("1234567890"), 11, 0, S("can't happen"));
1422    test(S("abcdefghijklmnopqrst"), 10, S("12345678901234567890"), 0, 0, S("abcdefghijklmnopqrst"));
1423    test(S("abcdefghijklmnopqrst"), 10, S("12345678901234567890"), 0, 1, S("abcdefghij1klmnopqrst"));
1424    test(S("abcdefghijklmnopqrst"), 10, S("12345678901234567890"), 0, 10, S("abcdefghij1234567890klmnopqrst"));
1425    test(S("abcdefghijklmnopqrst"), 10, S("12345678901234567890"), 0, 19, S("abcdefghij1234567890123456789klmnopqrst"));
1426    test(S("abcdefghijklmnopqrst"), 10, S("12345678901234567890"), 0, 20, S("abcdefghij12345678901234567890klmnopqrst"));
1427    test(S("abcdefghijklmnopqrst"), 10, S("12345678901234567890"), 0, 21, S("abcdefghij12345678901234567890klmnopqrst"));
1428    test(S("abcdefghijklmnopqrst"), 10, S("12345678901234567890"), 1, 0, S("abcdefghijklmnopqrst"));
1429    test(S("abcdefghijklmnopqrst"), 10, S("12345678901234567890"), 1, 1, S("abcdefghij2klmnopqrst"));
1430    test(S("abcdefghijklmnopqrst"), 10, S("12345678901234567890"), 1, 9, S("abcdefghij234567890klmnopqrst"));
1431    test(S("abcdefghijklmnopqrst"), 10, S("12345678901234567890"), 1, 18, S("abcdefghij234567890123456789klmnopqrst"));
1432    test(S("abcdefghijklmnopqrst"), 10, S("12345678901234567890"), 1, 19, S("abcdefghij2345678901234567890klmnopqrst"));
1433    test(S("abcdefghijklmnopqrst"), 10, S("12345678901234567890"), 1, 20, S("abcdefghij2345678901234567890klmnopqrst"));
1434    test(S("abcdefghijklmnopqrst"), 10, S("12345678901234567890"), 10, 0, S("abcdefghijklmnopqrst"));
1435    test(S("abcdefghijklmnopqrst"), 10, S("12345678901234567890"), 10, 1, S("abcdefghij1klmnopqrst"));
1436    test(S("abcdefghijklmnopqrst"), 10, S("12345678901234567890"), 10, 5, S("abcdefghij12345klmnopqrst"));
1437    test(S("abcdefghijklmnopqrst"), 10, S("12345678901234567890"), 10, 9, S("abcdefghij123456789klmnopqrst"));
1438}
1439
1440template <class S>
1441void test25()
1442{
1443    test(S("abcdefghijklmnopqrst"), 10, S("12345678901234567890"), 10, 10, S("abcdefghij1234567890klmnopqrst"));
1444    test(S("abcdefghijklmnopqrst"), 10, S("12345678901234567890"), 10, 11, S("abcdefghij1234567890klmnopqrst"));
1445    test(S("abcdefghijklmnopqrst"), 10, S("12345678901234567890"), 19, 0, S("abcdefghijklmnopqrst"));
1446    test(S("abcdefghijklmnopqrst"), 10, S("12345678901234567890"), 19, 1, S("abcdefghij0klmnopqrst"));
1447    test(S("abcdefghijklmnopqrst"), 10, S("12345678901234567890"), 19, 2, S("abcdefghij0klmnopqrst"));
1448    test(S("abcdefghijklmnopqrst"), 10, S("12345678901234567890"), 20, 0, S("abcdefghijklmnopqrst"));
1449    test(S("abcdefghijklmnopqrst"), 10, S("12345678901234567890"), 20, 1, S("abcdefghijklmnopqrst"));
1450    test(S("abcdefghijklmnopqrst"), 10, S("12345678901234567890"), 21, 0, S("can't happen"));
1451    test(S("abcdefghijklmnopqrst"), 19, S(""), 0, 0, S("abcdefghijklmnopqrst"));
1452    test(S("abcdefghijklmnopqrst"), 19, S(""), 0, 1, S("abcdefghijklmnopqrst"));
1453    test(S("abcdefghijklmnopqrst"), 19, S(""), 1, 0, S("can't happen"));
1454    test(S("abcdefghijklmnopqrst"), 19, S("12345"), 0, 0, S("abcdefghijklmnopqrst"));
1455    test(S("abcdefghijklmnopqrst"), 19, S("12345"), 0, 1, S("abcdefghijklmnopqrs1t"));
1456    test(S("abcdefghijklmnopqrst"), 19, S("12345"), 0, 2, S("abcdefghijklmnopqrs12t"));
1457    test(S("abcdefghijklmnopqrst"), 19, S("12345"), 0, 4, S("abcdefghijklmnopqrs1234t"));
1458    test(S("abcdefghijklmnopqrst"), 19, S("12345"), 0, 5, S("abcdefghijklmnopqrs12345t"));
1459    test(S("abcdefghijklmnopqrst"), 19, S("12345"), 0, 6, S("abcdefghijklmnopqrs12345t"));
1460    test(S("abcdefghijklmnopqrst"), 19, S("12345"), 1, 0, S("abcdefghijklmnopqrst"));
1461    test(S("abcdefghijklmnopqrst"), 19, S("12345"), 1, 1, S("abcdefghijklmnopqrs2t"));
1462    test(S("abcdefghijklmnopqrst"), 19, S("12345"), 1, 2, S("abcdefghijklmnopqrs23t"));
1463    test(S("abcdefghijklmnopqrst"), 19, S("12345"), 1, 3, S("abcdefghijklmnopqrs234t"));
1464    test(S("abcdefghijklmnopqrst"), 19, S("12345"), 1, 4, S("abcdefghijklmnopqrs2345t"));
1465    test(S("abcdefghijklmnopqrst"), 19, S("12345"), 1, 5, S("abcdefghijklmnopqrs2345t"));
1466    test(S("abcdefghijklmnopqrst"), 19, S("12345"), 2, 0, S("abcdefghijklmnopqrst"));
1467    test(S("abcdefghijklmnopqrst"), 19, S("12345"), 2, 1, S("abcdefghijklmnopqrs3t"));
1468    test(S("abcdefghijklmnopqrst"), 19, S("12345"), 2, 2, S("abcdefghijklmnopqrs34t"));
1469    test(S("abcdefghijklmnopqrst"), 19, S("12345"), 2, 3, S("abcdefghijklmnopqrs345t"));
1470    test(S("abcdefghijklmnopqrst"), 19, S("12345"), 2, 4, S("abcdefghijklmnopqrs345t"));
1471    test(S("abcdefghijklmnopqrst"), 19, S("12345"), 4, 0, S("abcdefghijklmnopqrst"));
1472    test(S("abcdefghijklmnopqrst"), 19, S("12345"), 4, 1, S("abcdefghijklmnopqrs5t"));
1473    test(S("abcdefghijklmnopqrst"), 19, S("12345"), 4, 2, S("abcdefghijklmnopqrs5t"));
1474    test(S("abcdefghijklmnopqrst"), 19, S("12345"), 5, 0, S("abcdefghijklmnopqrst"));
1475    test(S("abcdefghijklmnopqrst"), 19, S("12345"), 5, 1, S("abcdefghijklmnopqrst"));
1476    test(S("abcdefghijklmnopqrst"), 19, S("12345"), 6, 0, S("can't happen"));
1477    test(S("abcdefghijklmnopqrst"), 19, S("1234567890"), 0, 0, S("abcdefghijklmnopqrst"));
1478    test(S("abcdefghijklmnopqrst"), 19, S("1234567890"), 0, 1, S("abcdefghijklmnopqrs1t"));
1479    test(S("abcdefghijklmnopqrst"), 19, S("1234567890"), 0, 5, S("abcdefghijklmnopqrs12345t"));
1480    test(S("abcdefghijklmnopqrst"), 19, S("1234567890"), 0, 9, S("abcdefghijklmnopqrs123456789t"));
1481    test(S("abcdefghijklmnopqrst"), 19, S("1234567890"), 0, 10, S("abcdefghijklmnopqrs1234567890t"));
1482    test(S("abcdefghijklmnopqrst"), 19, S("1234567890"), 0, 11, S("abcdefghijklmnopqrs1234567890t"));
1483    test(S("abcdefghijklmnopqrst"), 19, S("1234567890"), 1, 0, S("abcdefghijklmnopqrst"));
1484    test(S("abcdefghijklmnopqrst"), 19, S("1234567890"), 1, 1, S("abcdefghijklmnopqrs2t"));
1485    test(S("abcdefghijklmnopqrst"), 19, S("1234567890"), 1, 4, S("abcdefghijklmnopqrs2345t"));
1486    test(S("abcdefghijklmnopqrst"), 19, S("1234567890"), 1, 8, S("abcdefghijklmnopqrs23456789t"));
1487    test(S("abcdefghijklmnopqrst"), 19, S("1234567890"), 1, 9, S("abcdefghijklmnopqrs234567890t"));
1488    test(S("abcdefghijklmnopqrst"), 19, S("1234567890"), 1, 10, S("abcdefghijklmnopqrs234567890t"));
1489    test(S("abcdefghijklmnopqrst"), 19, S("1234567890"), 5, 0, S("abcdefghijklmnopqrst"));
1490    test(S("abcdefghijklmnopqrst"), 19, S("1234567890"), 5, 1, S("abcdefghijklmnopqrs6t"));
1491    test(S("abcdefghijklmnopqrst"), 19, S("1234567890"), 5, 2, S("abcdefghijklmnopqrs67t"));
1492    test(S("abcdefghijklmnopqrst"), 19, S("1234567890"), 5, 4, S("abcdefghijklmnopqrs6789t"));
1493}
1494
1495template <class S>
1496void test26()
1497{
1498    test(S("abcdefghijklmnopqrst"), 19, S("1234567890"), 5, 5, S("abcdefghijklmnopqrs67890t"));
1499    test(S("abcdefghijklmnopqrst"), 19, S("1234567890"), 5, 6, S("abcdefghijklmnopqrs67890t"));
1500    test(S("abcdefghijklmnopqrst"), 19, S("1234567890"), 9, 0, S("abcdefghijklmnopqrst"));
1501    test(S("abcdefghijklmnopqrst"), 19, S("1234567890"), 9, 1, S("abcdefghijklmnopqrs0t"));
1502    test(S("abcdefghijklmnopqrst"), 19, S("1234567890"), 9, 2, S("abcdefghijklmnopqrs0t"));
1503    test(S("abcdefghijklmnopqrst"), 19, S("1234567890"), 10, 0, S("abcdefghijklmnopqrst"));
1504    test(S("abcdefghijklmnopqrst"), 19, S("1234567890"), 10, 1, S("abcdefghijklmnopqrst"));
1505    test(S("abcdefghijklmnopqrst"), 19, S("1234567890"), 11, 0, S("can't happen"));
1506    test(S("abcdefghijklmnopqrst"), 19, S("12345678901234567890"), 0, 0, S("abcdefghijklmnopqrst"));
1507    test(S("abcdefghijklmnopqrst"), 19, S("12345678901234567890"), 0, 1, S("abcdefghijklmnopqrs1t"));
1508    test(S("abcdefghijklmnopqrst"), 19, S("12345678901234567890"), 0, 10, S("abcdefghijklmnopqrs1234567890t"));
1509    test(S("abcdefghijklmnopqrst"), 19, S("12345678901234567890"), 0, 19, S("abcdefghijklmnopqrs1234567890123456789t"));
1510    test(S("abcdefghijklmnopqrst"), 19, S("12345678901234567890"), 0, 20, S("abcdefghijklmnopqrs12345678901234567890t"));
1511    test(S("abcdefghijklmnopqrst"), 19, S("12345678901234567890"), 0, 21, S("abcdefghijklmnopqrs12345678901234567890t"));
1512    test(S("abcdefghijklmnopqrst"), 19, S("12345678901234567890"), 1, 0, S("abcdefghijklmnopqrst"));
1513    test(S("abcdefghijklmnopqrst"), 19, S("12345678901234567890"), 1, 1, S("abcdefghijklmnopqrs2t"));
1514    test(S("abcdefghijklmnopqrst"), 19, S("12345678901234567890"), 1, 9, S("abcdefghijklmnopqrs234567890t"));
1515    test(S("abcdefghijklmnopqrst"), 19, S("12345678901234567890"), 1, 18, S("abcdefghijklmnopqrs234567890123456789t"));
1516    test(S("abcdefghijklmnopqrst"), 19, S("12345678901234567890"), 1, 19, S("abcdefghijklmnopqrs2345678901234567890t"));
1517    test(S("abcdefghijklmnopqrst"), 19, S("12345678901234567890"), 1, 20, S("abcdefghijklmnopqrs2345678901234567890t"));
1518    test(S("abcdefghijklmnopqrst"), 19, S("12345678901234567890"), 10, 0, S("abcdefghijklmnopqrst"));
1519    test(S("abcdefghijklmnopqrst"), 19, S("12345678901234567890"), 10, 1, S("abcdefghijklmnopqrs1t"));
1520    test(S("abcdefghijklmnopqrst"), 19, S("12345678901234567890"), 10, 5, S("abcdefghijklmnopqrs12345t"));
1521    test(S("abcdefghijklmnopqrst"), 19, S("12345678901234567890"), 10, 9, S("abcdefghijklmnopqrs123456789t"));
1522    test(S("abcdefghijklmnopqrst"), 19, S("12345678901234567890"), 10, 10, S("abcdefghijklmnopqrs1234567890t"));
1523    test(S("abcdefghijklmnopqrst"), 19, S("12345678901234567890"), 10, 11, S("abcdefghijklmnopqrs1234567890t"));
1524    test(S("abcdefghijklmnopqrst"), 19, S("12345678901234567890"), 19, 0, S("abcdefghijklmnopqrst"));
1525    test(S("abcdefghijklmnopqrst"), 19, S("12345678901234567890"), 19, 1, S("abcdefghijklmnopqrs0t"));
1526    test(S("abcdefghijklmnopqrst"), 19, S("12345678901234567890"), 19, 2, S("abcdefghijklmnopqrs0t"));
1527    test(S("abcdefghijklmnopqrst"), 19, S("12345678901234567890"), 20, 0, S("abcdefghijklmnopqrst"));
1528    test(S("abcdefghijklmnopqrst"), 19, S("12345678901234567890"), 20, 1, S("abcdefghijklmnopqrst"));
1529    test(S("abcdefghijklmnopqrst"), 19, S("12345678901234567890"), 21, 0, S("can't happen"));
1530    test(S("abcdefghijklmnopqrst"), 20, S(""), 0, 0, S("abcdefghijklmnopqrst"));
1531    test(S("abcdefghijklmnopqrst"), 20, S(""), 0, 1, S("abcdefghijklmnopqrst"));
1532    test(S("abcdefghijklmnopqrst"), 20, S(""), 1, 0, S("can't happen"));
1533    test(S("abcdefghijklmnopqrst"), 20, S("12345"), 0, 0, S("abcdefghijklmnopqrst"));
1534    test(S("abcdefghijklmnopqrst"), 20, S("12345"), 0, 1, S("abcdefghijklmnopqrst1"));
1535    test(S("abcdefghijklmnopqrst"), 20, S("12345"), 0, 2, S("abcdefghijklmnopqrst12"));
1536    test(S("abcdefghijklmnopqrst"), 20, S("12345"), 0, 4, S("abcdefghijklmnopqrst1234"));
1537    test(S("abcdefghijklmnopqrst"), 20, S("12345"), 0, 5, S("abcdefghijklmnopqrst12345"));
1538    test(S("abcdefghijklmnopqrst"), 20, S("12345"), 0, 6, S("abcdefghijklmnopqrst12345"));
1539    test(S("abcdefghijklmnopqrst"), 20, S("12345"), 1, 0, S("abcdefghijklmnopqrst"));
1540    test(S("abcdefghijklmnopqrst"), 20, S("12345"), 1, 1, S("abcdefghijklmnopqrst2"));
1541    test(S("abcdefghijklmnopqrst"), 20, S("12345"), 1, 2, S("abcdefghijklmnopqrst23"));
1542    test(S("abcdefghijklmnopqrst"), 20, S("12345"), 1, 3, S("abcdefghijklmnopqrst234"));
1543    test(S("abcdefghijklmnopqrst"), 20, S("12345"), 1, 4, S("abcdefghijklmnopqrst2345"));
1544    test(S("abcdefghijklmnopqrst"), 20, S("12345"), 1, 5, S("abcdefghijklmnopqrst2345"));
1545    test(S("abcdefghijklmnopqrst"), 20, S("12345"), 2, 0, S("abcdefghijklmnopqrst"));
1546    test(S("abcdefghijklmnopqrst"), 20, S("12345"), 2, 1, S("abcdefghijklmnopqrst3"));
1547    test(S("abcdefghijklmnopqrst"), 20, S("12345"), 2, 2, S("abcdefghijklmnopqrst34"));
1548}
1549
1550template <class S>
1551void test27()
1552{
1553    test(S("abcdefghijklmnopqrst"), 20, S("12345"), 2, 3, S("abcdefghijklmnopqrst345"));
1554    test(S("abcdefghijklmnopqrst"), 20, S("12345"), 2, 4, S("abcdefghijklmnopqrst345"));
1555    test(S("abcdefghijklmnopqrst"), 20, S("12345"), 4, 0, S("abcdefghijklmnopqrst"));
1556    test(S("abcdefghijklmnopqrst"), 20, S("12345"), 4, 1, S("abcdefghijklmnopqrst5"));
1557    test(S("abcdefghijklmnopqrst"), 20, S("12345"), 4, 2, S("abcdefghijklmnopqrst5"));
1558    test(S("abcdefghijklmnopqrst"), 20, S("12345"), 5, 0, S("abcdefghijklmnopqrst"));
1559    test(S("abcdefghijklmnopqrst"), 20, S("12345"), 5, 1, S("abcdefghijklmnopqrst"));
1560    test(S("abcdefghijklmnopqrst"), 20, S("12345"), 6, 0, S("can't happen"));
1561    test(S("abcdefghijklmnopqrst"), 20, S("1234567890"), 0, 0, S("abcdefghijklmnopqrst"));
1562    test(S("abcdefghijklmnopqrst"), 20, S("1234567890"), 0, 1, S("abcdefghijklmnopqrst1"));
1563    test(S("abcdefghijklmnopqrst"), 20, S("1234567890"), 0, 5, S("abcdefghijklmnopqrst12345"));
1564    test(S("abcdefghijklmnopqrst"), 20, S("1234567890"), 0, 9, S("abcdefghijklmnopqrst123456789"));
1565    test(S("abcdefghijklmnopqrst"), 20, S("1234567890"), 0, 10, S("abcdefghijklmnopqrst1234567890"));
1566    test(S("abcdefghijklmnopqrst"), 20, S("1234567890"), 0, 11, S("abcdefghijklmnopqrst1234567890"));
1567    test(S("abcdefghijklmnopqrst"), 20, S("1234567890"), 1, 0, S("abcdefghijklmnopqrst"));
1568    test(S("abcdefghijklmnopqrst"), 20, S("1234567890"), 1, 1, S("abcdefghijklmnopqrst2"));
1569    test(S("abcdefghijklmnopqrst"), 20, S("1234567890"), 1, 4, S("abcdefghijklmnopqrst2345"));
1570    test(S("abcdefghijklmnopqrst"), 20, S("1234567890"), 1, 8, S("abcdefghijklmnopqrst23456789"));
1571    test(S("abcdefghijklmnopqrst"), 20, S("1234567890"), 1, 9, S("abcdefghijklmnopqrst234567890"));
1572    test(S("abcdefghijklmnopqrst"), 20, S("1234567890"), 1, 10, S("abcdefghijklmnopqrst234567890"));
1573    test(S("abcdefghijklmnopqrst"), 20, S("1234567890"), 5, 0, S("abcdefghijklmnopqrst"));
1574    test(S("abcdefghijklmnopqrst"), 20, S("1234567890"), 5, 1, S("abcdefghijklmnopqrst6"));
1575    test(S("abcdefghijklmnopqrst"), 20, S("1234567890"), 5, 2, S("abcdefghijklmnopqrst67"));
1576    test(S("abcdefghijklmnopqrst"), 20, S("1234567890"), 5, 4, S("abcdefghijklmnopqrst6789"));
1577    test(S("abcdefghijklmnopqrst"), 20, S("1234567890"), 5, 5, S("abcdefghijklmnopqrst67890"));
1578    test(S("abcdefghijklmnopqrst"), 20, S("1234567890"), 5, 6, S("abcdefghijklmnopqrst67890"));
1579    test(S("abcdefghijklmnopqrst"), 20, S("1234567890"), 9, 0, S("abcdefghijklmnopqrst"));
1580    test(S("abcdefghijklmnopqrst"), 20, S("1234567890"), 9, 1, S("abcdefghijklmnopqrst0"));
1581    test(S("abcdefghijklmnopqrst"), 20, S("1234567890"), 9, 2, S("abcdefghijklmnopqrst0"));
1582    test(S("abcdefghijklmnopqrst"), 20, S("1234567890"), 10, 0, S("abcdefghijklmnopqrst"));
1583    test(S("abcdefghijklmnopqrst"), 20, S("1234567890"), 10, 1, S("abcdefghijklmnopqrst"));
1584    test(S("abcdefghijklmnopqrst"), 20, S("1234567890"), 11, 0, S("can't happen"));
1585    test(S("abcdefghijklmnopqrst"), 20, S("12345678901234567890"), 0, 0, S("abcdefghijklmnopqrst"));
1586    test(S("abcdefghijklmnopqrst"), 20, S("12345678901234567890"), 0, 1, S("abcdefghijklmnopqrst1"));
1587    test(S("abcdefghijklmnopqrst"), 20, S("12345678901234567890"), 0, 10, S("abcdefghijklmnopqrst1234567890"));
1588    test(S("abcdefghijklmnopqrst"), 20, S("12345678901234567890"), 0, 19, S("abcdefghijklmnopqrst1234567890123456789"));
1589    test(S("abcdefghijklmnopqrst"), 20, S("12345678901234567890"), 0, 20, S("abcdefghijklmnopqrst12345678901234567890"));
1590    test(S("abcdefghijklmnopqrst"), 20, S("12345678901234567890"), 0, 21, S("abcdefghijklmnopqrst12345678901234567890"));
1591    test(S("abcdefghijklmnopqrst"), 20, S("12345678901234567890"), 1, 0, S("abcdefghijklmnopqrst"));
1592    test(S("abcdefghijklmnopqrst"), 20, S("12345678901234567890"), 1, 1, S("abcdefghijklmnopqrst2"));
1593    test(S("abcdefghijklmnopqrst"), 20, S("12345678901234567890"), 1, 9, S("abcdefghijklmnopqrst234567890"));
1594    test(S("abcdefghijklmnopqrst"), 20, S("12345678901234567890"), 1, 18, S("abcdefghijklmnopqrst234567890123456789"));
1595    test(S("abcdefghijklmnopqrst"), 20, S("12345678901234567890"), 1, 19, S("abcdefghijklmnopqrst2345678901234567890"));
1596    test(S("abcdefghijklmnopqrst"), 20, S("12345678901234567890"), 1, 20, S("abcdefghijklmnopqrst2345678901234567890"));
1597    test(S("abcdefghijklmnopqrst"), 20, S("12345678901234567890"), 10, 0, S("abcdefghijklmnopqrst"));
1598    test(S("abcdefghijklmnopqrst"), 20, S("12345678901234567890"), 10, 1, S("abcdefghijklmnopqrst1"));
1599    test(S("abcdefghijklmnopqrst"), 20, S("12345678901234567890"), 10, 5, S("abcdefghijklmnopqrst12345"));
1600    test(S("abcdefghijklmnopqrst"), 20, S("12345678901234567890"), 10, 9, S("abcdefghijklmnopqrst123456789"));
1601    test(S("abcdefghijklmnopqrst"), 20, S("12345678901234567890"), 10, 10, S("abcdefghijklmnopqrst1234567890"));
1602    test(S("abcdefghijklmnopqrst"), 20, S("12345678901234567890"), 10, 11, S("abcdefghijklmnopqrst1234567890"));
1603}
1604
1605template <class S>
1606void test28()
1607{
1608    test(S("abcdefghijklmnopqrst"), 20, S("12345678901234567890"), 19, 0, S("abcdefghijklmnopqrst"));
1609    test(S("abcdefghijklmnopqrst"), 20, S("12345678901234567890"), 19, 1, S("abcdefghijklmnopqrst0"));
1610    test(S("abcdefghijklmnopqrst"), 20, S("12345678901234567890"), 19, 2, S("abcdefghijklmnopqrst0"));
1611    test(S("abcdefghijklmnopqrst"), 20, S("12345678901234567890"), 20, 0, S("abcdefghijklmnopqrst"));
1612    test(S("abcdefghijklmnopqrst"), 20, S("12345678901234567890"), 20, 1, S("abcdefghijklmnopqrst"));
1613    test(S("abcdefghijklmnopqrst"), 20, S("12345678901234567890"), 21, 0, S("can't happen"));
1614    test(S("abcdefghijklmnopqrst"), 21, S(""), 0, 0, S("can't happen"));
1615    test(S("abcdefghijklmnopqrst"), 21, S(""), 0, 1, S("can't happen"));
1616    test(S("abcdefghijklmnopqrst"), 21, S(""), 1, 0, S("can't happen"));
1617    test(S("abcdefghijklmnopqrst"), 21, S("12345"), 0, 0, S("can't happen"));
1618    test(S("abcdefghijklmnopqrst"), 21, S("12345"), 0, 1, S("can't happen"));
1619    test(S("abcdefghijklmnopqrst"), 21, S("12345"), 0, 2, S("can't happen"));
1620    test(S("abcdefghijklmnopqrst"), 21, S("12345"), 0, 4, S("can't happen"));
1621    test(S("abcdefghijklmnopqrst"), 21, S("12345"), 0, 5, S("can't happen"));
1622    test(S("abcdefghijklmnopqrst"), 21, S("12345"), 0, 6, S("can't happen"));
1623    test(S("abcdefghijklmnopqrst"), 21, S("12345"), 1, 0, S("can't happen"));
1624    test(S("abcdefghijklmnopqrst"), 21, S("12345"), 1, 1, S("can't happen"));
1625    test(S("abcdefghijklmnopqrst"), 21, S("12345"), 1, 2, S("can't happen"));
1626    test(S("abcdefghijklmnopqrst"), 21, S("12345"), 1, 3, S("can't happen"));
1627    test(S("abcdefghijklmnopqrst"), 21, S("12345"), 1, 4, S("can't happen"));
1628    test(S("abcdefghijklmnopqrst"), 21, S("12345"), 1, 5, S("can't happen"));
1629    test(S("abcdefghijklmnopqrst"), 21, S("12345"), 2, 0, S("can't happen"));
1630    test(S("abcdefghijklmnopqrst"), 21, S("12345"), 2, 1, S("can't happen"));
1631    test(S("abcdefghijklmnopqrst"), 21, S("12345"), 2, 2, S("can't happen"));
1632    test(S("abcdefghijklmnopqrst"), 21, S("12345"), 2, 3, S("can't happen"));
1633    test(S("abcdefghijklmnopqrst"), 21, S("12345"), 2, 4, S("can't happen"));
1634    test(S("abcdefghijklmnopqrst"), 21, S("12345"), 4, 0, S("can't happen"));
1635    test(S("abcdefghijklmnopqrst"), 21, S("12345"), 4, 1, S("can't happen"));
1636    test(S("abcdefghijklmnopqrst"), 21, S("12345"), 4, 2, S("can't happen"));
1637    test(S("abcdefghijklmnopqrst"), 21, S("12345"), 5, 0, S("can't happen"));
1638    test(S("abcdefghijklmnopqrst"), 21, S("12345"), 5, 1, S("can't happen"));
1639    test(S("abcdefghijklmnopqrst"), 21, S("12345"), 6, 0, S("can't happen"));
1640    test(S("abcdefghijklmnopqrst"), 21, S("1234567890"), 0, 0, S("can't happen"));
1641    test(S("abcdefghijklmnopqrst"), 21, S("1234567890"), 0, 1, S("can't happen"));
1642    test(S("abcdefghijklmnopqrst"), 21, S("1234567890"), 0, 5, S("can't happen"));
1643    test(S("abcdefghijklmnopqrst"), 21, S("1234567890"), 0, 9, S("can't happen"));
1644    test(S("abcdefghijklmnopqrst"), 21, S("1234567890"), 0, 10, S("can't happen"));
1645    test(S("abcdefghijklmnopqrst"), 21, S("1234567890"), 0, 11, S("can't happen"));
1646    test(S("abcdefghijklmnopqrst"), 21, S("1234567890"), 1, 0, S("can't happen"));
1647    test(S("abcdefghijklmnopqrst"), 21, S("1234567890"), 1, 1, S("can't happen"));
1648    test(S("abcdefghijklmnopqrst"), 21, S("1234567890"), 1, 4, S("can't happen"));
1649    test(S("abcdefghijklmnopqrst"), 21, S("1234567890"), 1, 8, S("can't happen"));
1650    test(S("abcdefghijklmnopqrst"), 21, S("1234567890"), 1, 9, S("can't happen"));
1651    test(S("abcdefghijklmnopqrst"), 21, S("1234567890"), 1, 10, S("can't happen"));
1652    test(S("abcdefghijklmnopqrst"), 21, S("1234567890"), 5, 0, S("can't happen"));
1653    test(S("abcdefghijklmnopqrst"), 21, S("1234567890"), 5, 1, S("can't happen"));
1654    test(S("abcdefghijklmnopqrst"), 21, S("1234567890"), 5, 2, S("can't happen"));
1655    test(S("abcdefghijklmnopqrst"), 21, S("1234567890"), 5, 4, S("can't happen"));
1656    test(S("abcdefghijklmnopqrst"), 21, S("1234567890"), 5, 5, S("can't happen"));
1657    test(S("abcdefghijklmnopqrst"), 21, S("1234567890"), 5, 6, S("can't happen"));
1658}
1659
1660template <class S>
1661void test29()
1662{
1663    test(S("abcdefghijklmnopqrst"), 21, S("1234567890"), 9, 0, S("can't happen"));
1664    test(S("abcdefghijklmnopqrst"), 21, S("1234567890"), 9, 1, S("can't happen"));
1665    test(S("abcdefghijklmnopqrst"), 21, S("1234567890"), 9, 2, S("can't happen"));
1666    test(S("abcdefghijklmnopqrst"), 21, S("1234567890"), 10, 0, S("can't happen"));
1667    test(S("abcdefghijklmnopqrst"), 21, S("1234567890"), 10, 1, S("can't happen"));
1668    test(S("abcdefghijklmnopqrst"), 21, S("1234567890"), 11, 0, S("can't happen"));
1669    test(S("abcdefghijklmnopqrst"), 21, S("12345678901234567890"), 0, 0, S("can't happen"));
1670    test(S("abcdefghijklmnopqrst"), 21, S("12345678901234567890"), 0, 1, S("can't happen"));
1671    test(S("abcdefghijklmnopqrst"), 21, S("12345678901234567890"), 0, 10, S("can't happen"));
1672    test(S("abcdefghijklmnopqrst"), 21, S("12345678901234567890"), 0, 19, S("can't happen"));
1673    test(S("abcdefghijklmnopqrst"), 21, S("12345678901234567890"), 0, 20, S("can't happen"));
1674    test(S("abcdefghijklmnopqrst"), 21, S("12345678901234567890"), 0, 21, S("can't happen"));
1675    test(S("abcdefghijklmnopqrst"), 21, S("12345678901234567890"), 1, 0, S("can't happen"));
1676    test(S("abcdefghijklmnopqrst"), 21, S("12345678901234567890"), 1, 1, S("can't happen"));
1677    test(S("abcdefghijklmnopqrst"), 21, S("12345678901234567890"), 1, 9, S("can't happen"));
1678    test(S("abcdefghijklmnopqrst"), 21, S("12345678901234567890"), 1, 18, S("can't happen"));
1679    test(S("abcdefghijklmnopqrst"), 21, S("12345678901234567890"), 1, 19, S("can't happen"));
1680    test(S("abcdefghijklmnopqrst"), 21, S("12345678901234567890"), 1, 20, S("can't happen"));
1681    test(S("abcdefghijklmnopqrst"), 21, S("12345678901234567890"), 10, 0, S("can't happen"));
1682    test(S("abcdefghijklmnopqrst"), 21, S("12345678901234567890"), 10, 1, S("can't happen"));
1683    test(S("abcdefghijklmnopqrst"), 21, S("12345678901234567890"), 10, 5, S("can't happen"));
1684    test(S("abcdefghijklmnopqrst"), 21, S("12345678901234567890"), 10, 9, S("can't happen"));
1685    test(S("abcdefghijklmnopqrst"), 21, S("12345678901234567890"), 10, 10, S("can't happen"));
1686    test(S("abcdefghijklmnopqrst"), 21, S("12345678901234567890"), 10, 11, S("can't happen"));
1687    test(S("abcdefghijklmnopqrst"), 21, S("12345678901234567890"), 19, 0, S("can't happen"));
1688    test(S("abcdefghijklmnopqrst"), 21, S("12345678901234567890"), 19, 1, S("can't happen"));
1689    test(S("abcdefghijklmnopqrst"), 21, S("12345678901234567890"), 19, 2, S("can't happen"));
1690    test(S("abcdefghijklmnopqrst"), 21, S("12345678901234567890"), 20, 0, S("can't happen"));
1691    test(S("abcdefghijklmnopqrst"), 21, S("12345678901234567890"), 20, 1, S("can't happen"));
1692    test(S("abcdefghijklmnopqrst"), 21, S("12345678901234567890"), 21, 0, S("can't happen"));
1693}
1694
1695template <class S>
1696void test30()
1697{
1698    test_npos(S(""), 0, S("12345678901234567890"),  0, S("12345678901234567890"));
1699    test_npos(S(""), 0, S("12345678901234567890"),  1, S( "2345678901234567890"));
1700    test_npos(S(""), 0, S("12345678901234567890"),  2, S(  "345678901234567890"));
1701    test_npos(S(""), 0, S("12345678901234567890"),  3, S(   "45678901234567890"));
1702    test_npos(S(""), 0, S("12345678901234567890"),  5, S(     "678901234567890"));
1703    test_npos(S(""), 0, S("12345678901234567890"), 10, S(          "1234567890"));
1704    test_npos(S(""), 0, S("12345678901234567890"), 21, S("can't happen"));
1705    test_npos(S("abcdefghijklmnopqrst"), 10, S("12345"), 0, S("abcdefghij12345klmnopqrst"));
1706    test_npos(S("abcdefghijklmnopqrst"), 10, S("12345"), 1, S("abcdefghij2345klmnopqrst"));
1707    test_npos(S("abcdefghijklmnopqrst"), 10, S("12345"), 3, S("abcdefghij45klmnopqrst"));
1708    test_npos(S("abcdefghijklmnopqrst"), 10, S("12345"), 5, S("abcdefghijklmnopqrst"));
1709    test_npos(S("abcdefghijklmnopqrst"), 10, S("12345"), 6, S("can't happen"));
1710}
1711
1712int main()
1713{
1714    {
1715    typedef std::string S;
1716    test0<S>();
1717    test1<S>();
1718    test2<S>();
1719    test3<S>();
1720    test4<S>();
1721    test5<S>();
1722    test6<S>();
1723    test7<S>();
1724    test8<S>();
1725    test9<S>();
1726    test10<S>();
1727    test11<S>();
1728    test12<S>();
1729    test13<S>();
1730    test14<S>();
1731    test15<S>();
1732    test16<S>();
1733    test17<S>();
1734    test18<S>();
1735    test19<S>();
1736    test20<S>();
1737    test21<S>();
1738    test22<S>();
1739    test23<S>();
1740    test24<S>();
1741    test25<S>();
1742    test26<S>();
1743    test27<S>();
1744    test28<S>();
1745    test29<S>();
1746    test30<S>();
1747    }
1748#if __cplusplus >= 201103L
1749    {
1750    typedef std::basic_string<char, std::char_traits<char>, min_allocator<char>> S;
1751    test0<S>();
1752    test1<S>();
1753    test2<S>();
1754    test3<S>();
1755    test4<S>();
1756    test5<S>();
1757    test6<S>();
1758    test7<S>();
1759    test8<S>();
1760    test9<S>();
1761    test10<S>();
1762    test11<S>();
1763    test12<S>();
1764    test13<S>();
1765    test14<S>();
1766    test15<S>();
1767    test16<S>();
1768    test17<S>();
1769    test18<S>();
1770    test19<S>();
1771    test20<S>();
1772    test21<S>();
1773    test22<S>();
1774    test23<S>();
1775    test24<S>();
1776    test25<S>();
1777    test26<S>();
1778    test27<S>();
1779    test28<S>();
1780    test29<S>();
1781    test30<S>();
1782    }
1783#endif
1784}
1785