#include <iostream>
#include <cstring>
using namespace std;
 
class PatternGenerator2Exception {};
 
class PatternGenerator2
{
private:
	int *_src;
	int *_flag;
	int *_indexes;
	int *_list;
	int _srcsize;
	int _len;
	int _count;
	PatternGenerator2(int srcsize, int len, int c) 
				: _srcsize(srcsize), _len(len), _count(c) {
 
		if (_srcsize < 2 || _len < 2 || _srcsize < _len) {
			throw PatternGenerator2Exception();
		}		
		_src = new int[_srcsize];
		_flag = new int[_srcsize];
 
		_list = new int[_len];
		_indexes = new int[len];
 
		for (int i = 0; i < _srcsize; i++) {
			_flag[i] = 0;
		}		
	}
public:
 
	PatternGenerator2(int srcsize, int len) 
			: PatternGenerator2(srcsize, len, 0) {
 
		for (int i = 0; i < _srcsize; i++) {
			_src[i] = i + 1;
		}		
 
		reset();
	}
 
	PatternGenerator2(int size) 
			: PatternGenerator2(size, size) {
	}
 
	PatternGenerator2(const int *sortedsrc, int srcsize, int len)
			: PatternGenerator2(srcsize, len, 0) {
 
		memcpy(_src, sortedsrc, sizeof(int) * _srcsize);
 
		reset();
	}
 
	~PatternGenerator2() {
		delete [] _src;
		delete [] _flag;
		delete [] _list;
		delete [] _indexes;
	}
 
	int length()     const { return _len; }
	int sourcesize() const { return _srcsize; }
	int count()      const { return _count; }
 
	void reset() {
		for (int i = 0; i < _len; i++) {
			_flag[_indexes[i]] = 0;
		}
		for (int i = 0; i < _len; i++) {
			_indexes[i] = i;
			_list[i] = _src[_indexes[i]];
			_flag[_indexes[i]] = 1;
		}
		_count = 0;
	}
 
	int hasNext() {
		if (_count == 0) {
			return 1;
		}
		for (int i = 0; i < _len; i++) {
			if (_src[_indexes[i]] != _src[_srcsize - i - 1]) {
				return 1;
			}
		}
		return 0;
	}
 
	const int* next() {
 
		if (_count == 0) {
			_count++;
			return _list;
		}
 
		int i, j, b, f;
 
		i = _len - 1;
		_flag[_indexes[i]] = 0;
 
		f = 1;
 
		for (;;) {
			if (f) {
				b = _src[_indexes[i]];
				for (j = _indexes[i] + 1; j < _srcsize; j++) {
					if (_flag[j] == 0 && _src[j] != b) {
						break;
					}
				}
			} else {
				for (j = 0; j < _srcsize; j++) {
					if (_flag[j] == 0) {
						break;
					}
				}
				f = 1;
			}
			if (j == _srcsize) {
				i--;
				if (i < 0) {
					reset();
					break;
				} else {
					_flag[_indexes[i]] = 0;
				}
			} else {
				_indexes[i] = j;
				_list[i] = _src[_indexes[i]];
				_flag[_indexes[i]] = 1;
				i++;
				if (i == _len) {
					// kakutei
					break;
				} else {
					f = 0;
				}
			}
		}
		_count++;
		return _list;
	}
};
 
int nCr(int n, int r) {
	if (n < 0 || r < 0 || n < r) {
		return 0;
	}
	if (n - r < r) {
		r = n - r;
	}
	int c = 1;
	for (int i = 1; i <= r; i++) {
		c *= n;
		c /= i;
		n--;
	}
	return c;
}
 
int nPr(int n, int r) {
	if (n < 0 || r < 0 || n < r) {
		return 0;
	}
	int p = 1;
	while (r > 0) {
		p *= n;
		n--;
		r--;
	}
	return p;
}
 
int main() {
 
	int src[] = { 1, 2, 2, 5};
	int len = sizeof(src) / sizeof(src[0]);
	PatternGenerator2 gen(4);
	PatternGenerator2 gen2(5, 3);
	PatternGenerator2 gen3(src, len, len);
 
	for (int i = 0; i < 25; i++) {
		const int *k = gen.next();
		cout.fill('_');
		cout.width(8);
		cout << gen.count() << ": ";
		for (int j = 0; j < gen.length(); j++) {
			cout << "_ABCDEFGHIJKLMNOPQRSTUVWXYZ"[k[j]];
		}
		cout << endl;
	}
 
	cout << endl;
 
	gen.reset();
 
	while (gen.hasNext()) {
		const int *k = gen.next();
		cout.fill('.');
		cout.width(8);
		cout << gen.count() << ": ";
		for (int j = 0; j < gen.length(); j++) {
			cout << "_ABCDEFGHIJKLMNOPQRSTUVWXYZ"[k[j]];
		}
		cout << endl;
	}
 
	cout << endl << endl;;
 
	while (gen2.hasNext()) {
		const int *k = gen2.next();
		cout.fill('*');
		cout.width(8);
		cout << gen2.count() << ": ";
		for (int j = 0; j < gen2.length(); j++) {
			cout << "_ABCDEFGHIJKLMNOPQRSTUVWXYZ"[k[j]];
		}
		cout << endl;
	}
 
	cout << endl << endl;
 
	while (gen3.hasNext()) {
		const int *k = gen3.next();
		cout.fill('#');
		cout.width(8);
		cout << gen3.count() << ": ";
		for (int j = 0; j < gen3.length(); j++) {
			cout << k[j];
		}
		cout << endl;
	}
 
	return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8Y3N0cmluZz4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmNsYXNzIFBhdHRlcm5HZW5lcmF0b3IyRXhjZXB0aW9uIHt9OwoKY2xhc3MgUGF0dGVybkdlbmVyYXRvcjIKewpwcml2YXRlOgoJaW50ICpfc3JjOwoJaW50ICpfZmxhZzsKCWludCAqX2luZGV4ZXM7CglpbnQgKl9saXN0OwoJaW50IF9zcmNzaXplOwoJaW50IF9sZW47CglpbnQgX2NvdW50OwoJUGF0dGVybkdlbmVyYXRvcjIoaW50IHNyY3NpemUsIGludCBsZW4sIGludCBjKSAKCQkJCTogX3NyY3NpemUoc3Jjc2l6ZSksIF9sZW4obGVuKSwgX2NvdW50KGMpIHsKCgkJaWYgKF9zcmNzaXplIDwgMiB8fCBfbGVuIDwgMiB8fCBfc3Jjc2l6ZSA8IF9sZW4pIHsKCQkJdGhyb3cgUGF0dGVybkdlbmVyYXRvcjJFeGNlcHRpb24oKTsKCQl9CQkKCQlfc3JjID0gbmV3IGludFtfc3Jjc2l6ZV07CgkJX2ZsYWcgPSBuZXcgaW50W19zcmNzaXplXTsKCgkJX2xpc3QgPSBuZXcgaW50W19sZW5dOwoJCV9pbmRleGVzID0gbmV3IGludFtsZW5dOwoJCQoJCWZvciAoaW50IGkgPSAwOyBpIDwgX3NyY3NpemU7IGkrKykgewoJCQlfZmxhZ1tpXSA9IDA7CgkJfQkJCgl9CnB1YmxpYzoKCglQYXR0ZXJuR2VuZXJhdG9yMihpbnQgc3Jjc2l6ZSwgaW50IGxlbikgCgkJCTogUGF0dGVybkdlbmVyYXRvcjIoc3Jjc2l6ZSwgbGVuLCAwKSB7CgoJCWZvciAoaW50IGkgPSAwOyBpIDwgX3NyY3NpemU7IGkrKykgewoJCQlfc3JjW2ldID0gaSArIDE7CgkJfQkJCgkJCgkJcmVzZXQoKTsKCX0KCQoJUGF0dGVybkdlbmVyYXRvcjIoaW50IHNpemUpIAoJCQk6IFBhdHRlcm5HZW5lcmF0b3IyKHNpemUsIHNpemUpIHsKCX0KCQoJUGF0dGVybkdlbmVyYXRvcjIoY29uc3QgaW50ICpzb3J0ZWRzcmMsIGludCBzcmNzaXplLCBpbnQgbGVuKQoJCQk6IFBhdHRlcm5HZW5lcmF0b3IyKHNyY3NpemUsIGxlbiwgMCkgewoKCQltZW1jcHkoX3NyYywgc29ydGVkc3JjLCBzaXplb2YoaW50KSAqIF9zcmNzaXplKTsKCQkKCQlyZXNldCgpOwoJfQoJCgl+UGF0dGVybkdlbmVyYXRvcjIoKSB7CgkJZGVsZXRlIFtdIF9zcmM7CgkJZGVsZXRlIFtdIF9mbGFnOwoJCWRlbGV0ZSBbXSBfbGlzdDsKCQlkZWxldGUgW10gX2luZGV4ZXM7Cgl9CgkKCWludCBsZW5ndGgoKSAgICAgY29uc3QgeyByZXR1cm4gX2xlbjsgfQoJaW50IHNvdXJjZXNpemUoKSBjb25zdCB7IHJldHVybiBfc3Jjc2l6ZTsgfQoJaW50IGNvdW50KCkgICAgICBjb25zdCB7IHJldHVybiBfY291bnQ7IH0KCQoJdm9pZCByZXNldCgpIHsKCQlmb3IgKGludCBpID0gMDsgaSA8IF9sZW47IGkrKykgewoJCQlfZmxhZ1tfaW5kZXhlc1tpXV0gPSAwOwoJCX0KCQlmb3IgKGludCBpID0gMDsgaSA8IF9sZW47IGkrKykgewoJCQlfaW5kZXhlc1tpXSA9IGk7CgkJCV9saXN0W2ldID0gX3NyY1tfaW5kZXhlc1tpXV07CgkJCV9mbGFnW19pbmRleGVzW2ldXSA9IDE7CgkJfQoJCV9jb3VudCA9IDA7Cgl9CgkKCWludCBoYXNOZXh0KCkgewoJCWlmIChfY291bnQgPT0gMCkgewoJCQlyZXR1cm4gMTsKCQl9CgkJZm9yIChpbnQgaSA9IDA7IGkgPCBfbGVuOyBpKyspIHsKCQkJaWYgKF9zcmNbX2luZGV4ZXNbaV1dICE9IF9zcmNbX3NyY3NpemUgLSBpIC0gMV0pIHsKCQkJCXJldHVybiAxOwoJCQl9CgkJfQoJCXJldHVybiAwOwoJfQoJCgljb25zdCBpbnQqIG5leHQoKSB7CgkJCgkJaWYgKF9jb3VudCA9PSAwKSB7CgkJCV9jb3VudCsrOwoJCQlyZXR1cm4gX2xpc3Q7CgkJfQoJCQoJCWludCBpLCBqLCBiLCBmOwoJCQoJCWkgPSBfbGVuIC0gMTsKCQlfZmxhZ1tfaW5kZXhlc1tpXV0gPSAwOwoJCQoJCWYgPSAxOwoJCQoJCWZvciAoOzspIHsKCQkJaWYgKGYpIHsKCQkJCWIgPSBfc3JjW19pbmRleGVzW2ldXTsKCQkJCWZvciAoaiA9IF9pbmRleGVzW2ldICsgMTsgaiA8IF9zcmNzaXplOyBqKyspIHsKCQkJCQlpZiAoX2ZsYWdbal0gPT0gMCAmJiBfc3JjW2pdICE9IGIpIHsKCQkJCQkJYnJlYWs7CgkJCQkJfQoJCQkJfQoJCQl9IGVsc2UgewoJCQkJZm9yIChqID0gMDsgaiA8IF9zcmNzaXplOyBqKyspIHsKCQkJCQlpZiAoX2ZsYWdbal0gPT0gMCkgewoJCQkJCQlicmVhazsKCQkJCQl9CgkJCQl9CgkJCQlmID0gMTsKCQkJfQoJCQlpZiAoaiA9PSBfc3Jjc2l6ZSkgewoJCQkJaS0tOwoJCQkJaWYgKGkgPCAwKSB7CgkJCQkJcmVzZXQoKTsKCQkJCQlicmVhazsKCQkJCX0gZWxzZSB7CgkJCQkJX2ZsYWdbX2luZGV4ZXNbaV1dID0gMDsKCQkJCX0KCQkJfSBlbHNlIHsKCQkJCV9pbmRleGVzW2ldID0gajsKCQkJCV9saXN0W2ldID0gX3NyY1tfaW5kZXhlc1tpXV07CgkJCQlfZmxhZ1tfaW5kZXhlc1tpXV0gPSAxOwoJCQkJaSsrOwoJCQkJaWYgKGkgPT0gX2xlbikgewoJCQkJCS8vIGtha3V0ZWkKCQkJCQlicmVhazsKCQkJCX0gZWxzZSB7CgkJCQkJZiA9IDA7CgkJCQl9CgkJCX0KCQl9CgkJX2NvdW50Kys7CgkJcmV0dXJuIF9saXN0OwoJfQp9OwoKaW50IG5DcihpbnQgbiwgaW50IHIpIHsKCWlmIChuIDwgMCB8fCByIDwgMCB8fCBuIDwgcikgewoJCXJldHVybiAwOwoJfQoJaWYgKG4gLSByIDwgcikgewoJCXIgPSBuIC0gcjsKCX0KCWludCBjID0gMTsKCWZvciAoaW50IGkgPSAxOyBpIDw9IHI7IGkrKykgewoJCWMgKj0gbjsKCQljIC89IGk7CgkJbi0tOwoJfQoJcmV0dXJuIGM7Cn0KCmludCBuUHIoaW50IG4sIGludCByKSB7CglpZiAobiA8IDAgfHwgciA8IDAgfHwgbiA8IHIpIHsKCQlyZXR1cm4gMDsKCX0KCWludCBwID0gMTsKCXdoaWxlIChyID4gMCkgewoJCXAgKj0gbjsKCQluLS07CgkJci0tOwoJfQoJcmV0dXJuIHA7Cn0KCmludCBtYWluKCkgewoJCglpbnQgc3JjW10gPSB7IDEsIDIsIDIsIDV9OwoJaW50IGxlbiA9IHNpemVvZihzcmMpIC8gc2l6ZW9mKHNyY1swXSk7CglQYXR0ZXJuR2VuZXJhdG9yMiBnZW4oNCk7CglQYXR0ZXJuR2VuZXJhdG9yMiBnZW4yKDUsIDMpOwoJUGF0dGVybkdlbmVyYXRvcjIgZ2VuMyhzcmMsIGxlbiwgbGVuKTsKCQoJZm9yIChpbnQgaSA9IDA7IGkgPCAyNTsgaSsrKSB7CgkJY29uc3QgaW50ICprID0gZ2VuLm5leHQoKTsKCQljb3V0LmZpbGwoJ18nKTsKCQljb3V0LndpZHRoKDgpOwoJCWNvdXQgPDwgZ2VuLmNvdW50KCkgPDwgIjogIjsKCQlmb3IgKGludCBqID0gMDsgaiA8IGdlbi5sZW5ndGgoKTsgaisrKSB7CgkJCWNvdXQgPDwgIl9BQkNERUZHSElKS0xNTk9QUVJTVFVWV1hZWiJba1tqXV07CgkJfQoJCWNvdXQgPDwgZW5kbDsKCX0KCQoJY291dCA8PCBlbmRsOwoJCglnZW4ucmVzZXQoKTsKCQoJd2hpbGUgKGdlbi5oYXNOZXh0KCkpIHsKCQljb25zdCBpbnQgKmsgPSBnZW4ubmV4dCgpOwoJCWNvdXQuZmlsbCgnLicpOwoJCWNvdXQud2lkdGgoOCk7CgkJY291dCA8PCBnZW4uY291bnQoKSA8PCAiOiAiOwoJCWZvciAoaW50IGogPSAwOyBqIDwgZ2VuLmxlbmd0aCgpOyBqKyspIHsKCQkJY291dCA8PCAiX0FCQ0RFRkdISUpLTE1OT1BRUlNUVVZXWFlaIltrW2pdXTsKCQl9CgkJY291dCA8PCBlbmRsOwoJfQoKCWNvdXQgPDwgZW5kbCA8PCBlbmRsOzsKCQoJd2hpbGUgKGdlbjIuaGFzTmV4dCgpKSB7CgkJY29uc3QgaW50ICprID0gZ2VuMi5uZXh0KCk7CgkJY291dC5maWxsKCcqJyk7CgkJY291dC53aWR0aCg4KTsKCQljb3V0IDw8IGdlbjIuY291bnQoKSA8PCAiOiAiOwoJCWZvciAoaW50IGogPSAwOyBqIDwgZ2VuMi5sZW5ndGgoKTsgaisrKSB7CgkJCWNvdXQgPDwgIl9BQkNERUZHSElKS0xNTk9QUVJTVFVWV1hZWiJba1tqXV07CgkJfQoJCWNvdXQgPDwgZW5kbDsKCX0KCQoJY291dCA8PCBlbmRsIDw8IGVuZGw7CgoJd2hpbGUgKGdlbjMuaGFzTmV4dCgpKSB7CgkJY29uc3QgaW50ICprID0gZ2VuMy5uZXh0KCk7CgkJY291dC5maWxsKCcjJyk7CgkJY291dC53aWR0aCg4KTsKCQljb3V0IDw8IGdlbjMuY291bnQoKSA8PCAiOiAiOwoJCWZvciAoaW50IGogPSAwOyBqIDwgZ2VuMy5sZW5ndGgoKTsgaisrKSB7CgkJCWNvdXQgPDwga1tqXTsKCQl9CgkJY291dCA8PCBlbmRsOwoJfQoJCglyZXR1cm4gMDsKfQ==