Implement LookAndSay function.

Epic Systems Interview Question for Software Engineer / Developers

3

of 3 votes

43
Answers
Implement LookAndSay function. For example, first, let user input a number, say 1. Then, the function will generate the next 10 numbers which satisfy this condition:
1, 11,21,1211,111221,312211...
explanation: first number 1, second number is one 1, so 11. Third number is two 1(previous number), so 21. next number one 2 one 1, so 1211 and so on...
- Kevin February 22, 2013 in United States | Report Duplicate | Flag | PURGE
Epic Systems Software Engineer / Developer Algorithm

Email me when people comment.

An error occurred in subscribing you.

Country: United States
Interview Type: Written Test

Email me when people comment.

An error occurred in subscribing you.

Comment hidden because of low score. Click to expand.

of 4 vote

Taken from Rosettacode org

public static String lookandsay(String number){
	StringBuilder result= new StringBuilder();
 
	char repeat= number.charAt(0);
	number= number.substring(1) + " ";
	int times= 1;
 
	for(char actual: number.toCharArray()){
		if(actual != repeat){
			result.append(times + "" + repeat);
			times= 1;
			repeat= actual;
		}else{
			times+= 1;
		}
	}
	return result.toString();
}

Testing

public static void main(String[] args){
	String num = "1"; 
 
	for (int i=1;i<=10;i++) {
		System.out.println(num);
		num = lookandsay(num);             
	}
}

Output

1
11
21
1211
111221
312211
13112221
1113213211
31131211131221
13211311123113112211

- Anonymous March 01, 2014 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 votes

a little bit hard to understand, but it is perfect solution.

- zyn468 April 13, 2014 | Flag

Comment hidden because of low score. Click to expand.

of 0 votes

Nice Solution but it will give StringIndexOutOfBoundException. To Avoid that, add this code snippet after For Loop:-

//For the end case
sb.append(times+""+repeat);

- Tushar April 15, 2014 | Flag

Comment hidden because of low score. Click to expand.

of 2 vote

Run Length Algorithm

- Rinku Goel February 24, 2013 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 votes

Refer this it ll be useful;;

if(i am wrong)
{
Forgive me;
}
else
{
Pay meeeeeeee...
}

kidding............

Sample code.:::

#include <stdio.h>
#include <stdlib.h>

int main()
{
char *a = malloc(2), *b = 0, *x, c;
int cnt, len = 1;

for (sprintf(a, "1"); (b = realloc(b, len * 2 + 1)); a = b, b = x) {
puts(x = a);
for (len = 0, cnt = 1; (c = *a); ) {
if (c == *++a)
cnt++;
else if (c) {
len += sprintf(b + len, "%d%c", cnt, c);
cnt = 1;
}
}
}

return 0;
}

output:

1
11
21
1211
111221
312211
13112221
1113213211
31131211131221
13211311123113112211
11131221133112132113212221
3113112221232112111312211312113211
1321132132111213122112311311222113111221131221
11131221131211131231121113112221121321132132211331222113112211
311311222113111231131112132112311321322112111312211312111322212311322113212221
132113213221133112132113311211131221121321131211132221123113112221131112311332111213211322211312113211
11131221131211132221232112111312212321123113112221121113122113111231133221121321132132211331121321231231121113122113322113111221131221
31131122211311123113321112131221123113112211121312211213211321322112311311222113311213212322211211131221131211132221232112111312111213111213211231131122212322211331222113112211
1321132132211331121321231231121113112221121321132122311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213122112311311123112111331121113122112132113213211121332212311322113212221
11131221131211132221232112111312111213111213211231132132211211131221131211221321123113213221123113112221131112311332211211131221131211132211121312211231131112311211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113121113123112112322111213211322211312113211
311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122211311122122111312211213211312111322211213211321322113311213212322211231131122211311123113223112111311222112132113311213211221121332211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221131112311311121321122112132231121113122113322113111221131221
132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113213221133122112231131122211211131221131112311332211211131221131211132221232112111312111213322112132113213221133112132113221321123113213221121113122123211211131221222112112322211231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122211211133112111311222112111312211312111322211213211321322113311213211331121113122122211211132213211231131122212322211331222113112211
111312211312111322212321121113121112131112132112311321322112111312212321121113122112131112131221121321132132211231131122211331121321232221121113122113121113222123112221221321132132211231131122211331121321232221123113112221131112311332111213122112311311123112112322211211131221131211132221232112111312211322111312211213211312111322211231131122111213122112311311221132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322212321121113122123211231131122113221123113221113122112132113213211121332212311322113212221
3113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213213211221113122113121113222112132113213221232112111312111213322112132113213221133112132123123112111311222112132113311213211221121332211231131122211311123113321112131221123113112221132231131122211211131221131112311332211213211321223112111311222112132113212221132221222112112322211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211132221121311121312211213211312111322211213211321322113311213212322211231131122211311123113321112131221123113112211121312211213211321222113222112132113223113112221121113122113121113123112112322111213211322211312113211
132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113212231121113112221121321132132211231232112311321322112311311222113111231133221121113122113121113221112131221123113111231121123222112132113213221133112132123123112111312111312212231131122211311123113322112111312211312111322111213122112311311123112112322211211131221131211132221232112111312111213111213211231132132211211131221232112111312212221121123222112132113213221133112132123123112111311222112132113213221132213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121132211332113221122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112311332211211133112111311222112111312211311123113322112111312211312111322212321121113121112133221121321132132211331121321231231121113112221121321132122311211131122211211131221131211322113322112111312211322132113213221123113112221131112311311121321122112132231121113122113322113111221131221
1113122113121113222123211211131211121311121321123113213221121113122123211211131221121311121312211213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121113222112131112131221121321131211132221121321132132211331121321232221123113112221131112311322311211131122211213211331121321122112133221121113122113121113222123211211131211121311121321123113111231131122112213211321322113311213212322211231131122211311123113223112111311222112132113311213211221121332211231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122113221122112133221121113122113121113222123211211131211121311121321123113213221121113122113121113222113221113122113121113222112132113213221232112111312111213322112311311222113111221221113122112132113121113222112311311222113111221132221231221132221222112112322211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331121321232221123123211231132132211231131122211331121321232221123113112221131112311332111213122112311311123112112322211211131221131211132221232112111312111213111213211231132132211211131221131211221321123113213221123113112221131112211322212322211231131122211322111312211312111322211213211321322113311213211331121113122122211211132213211231131122212322211331222113112211
31131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122211211133112111311222112111312211312111322211213211321322123211211131211121332211231131122211311122122111312211213211312111322211231131122211311123113322112111331121113112221121113122113111231133221121113122113121113222123211211131211121332211213211321322113311213211322132112311321322112111312212321121113122122211211232221123113112221131112311332111213122112311311123112111331121113122112132113311213211321222122111312211312111322212321121113121112133221121321132132211331121321132213211231132132211211131221232112111312212221121123222112132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113212231121113112221121321132122211322212221121123222112311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122211311123113322113223113112221131112311332211211131221131211132211121312211231131112311211232221121321132132211331221122311311222112111312211311123113322112132113213221133122211332111213112221133211322112211213322112111312211312111322212321121113121112131112132112311321322112111312212321121113122112131112131221121321132132211231131122211331121321232221121113122113121122132112311321322112111312211312111322211213111213122112132113121113222112132113213221133112132123222112311311222113111231132231121113112221121321133112132112211213322112111312211312111322212311222122132113213221123113112221133112132123222112111312211312111322212321121113121112133221121311121312211213211312111322211213211321322123211211131211121332211213211321322113311213212312311211131122211213211331121321122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311222113111221221113122112132113121113222112132113213221133122211332111213322112132113213221132231131122211311123113322112111312211312111322212321121113122123211231131122113221123113221113122112132113213211121332212311322113212221
13211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331121321232221123123211231132132211231131122211331121321232221123113112221131112311332111213122112311311123112112322211211131221131211132221232112111312211322111312211213211312111322211231131122111213122112311311221132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221232112111312211312113211223113112221131112311332111213122112311311123112112322211211131221131211132221232112111312211322111312211213211312111322211231131122111213122112311311221132211221121332211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321322113311213212322211322132113213221133112132123222112311311222113111231132231121113112221121321133112132112211213322112111312211312111322212311222122132113213221123113112221133112132123222112111312211312111322212311322123123112111321322123122113222122211211232221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112311332211211133112111311222112111312211311123113322112111312211312111322212321121113121112133221121321132132211331121321132213211231132132211211131221232112111312212221121123222112311311222113111231133211121321321122111312211312111322211213211321322123211211131211121332211231131122211311123113321112131221123113111231121123222112111331121113112221121113122113111231133221121113122113121113221112131221123113111231121123222112111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113111231133221121321132132211331221122311311222112111312211311123113322112111312211312111322212311322123123112112322211211131221131211132221132213211321322113311213212322211231131122211311123113321112131221123113112211121312211213211321222113222112132113223113112221121113122113121113123112112322111213211322211312113211
11131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211132221121311121312211213211312111322211213211321322113311213212322211231131122211311123113223112111311222112132113311213211221121332211211131221131211132221231122212213211321322112311311222113311213212322211211131221131211132221232112111312111213322112131112131221121321131211132221121321132132212321121113121112133221121321132132211331121321231231121113112221121321133112132112211213322112311311222113111231133211121312211231131122211322311311222112111312211311123113322112132113212231121113112221121321132122211322212221121123222112111312211312111322212321121113121112131112132112311321322112111312212321121113122112131112131221121321132132211231131122111213122112311311222113111221131221221321132132211331121321231231121113112221121321133112132112211213322112311311222113111231133211121312211231131122211322311311222112111312211311123113322112132113212231121113112221121321132122211322212221121123222112311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122111213122112311311222112111331121113112221121113122113121113222112132113213221232112111312111213322112311311222113111221221113122112132113121113222112311311222113111221132221231221132221222112112322211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312111322212321121113121112133221132211131221131211132221232112111312111213322112132113213221133112132113221321123113213221121113122123211211131221222112112322211231131122211311123113321112132132112211131221131211132221121321132132212321121113121112133221123113112221131112311332111213211322111213111213211231131211132211121311222113321132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331121321232221123123211231132132211231131122211331121321232221123113112221131112311332111213122112311311123112112322211211131221131211132221232112111312211322111312211213211312111322211231131122111213122112311311221132211221121332211213211321322113311213212312311211131211131221223113112221131112311332211211131221131211132211121312211231131112311211232221121321132132211331121321231231121113112221121321133112132112211213322112312321123113213221123113112221133112132123222112311311222113111231132231121113112221121321133112132112211213322112311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122111213122112311311221132211221121332211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312111322212311222122132113213221123113112221133112132123222112311311222113111231133211121321132211121311121321122112133221123113112221131112311332211322111312211312111322212321121113121112133221121321132132211331121321231231121113112221121321132122311211131122211211131221131211322113322112111312211322132113213221123113112221131112311311121321122112132231121113122113322113111221131221
3113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112311332211211133112111311222112111312211311123113322112111312211312111322212321121113121112133221121321132132211331121321132213211231132132211211131221232112111312212221121123222112311311222113111231133211121321321122111312211312111322211213211321322123211211131211121332211231131122211311123113321112131221123113111231121123222112111331121113112221121113122113111231133221121113122113121113221112131221123113111231121123222112111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321132132211322132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122211211133112111311222112111312211312111322211213211321223112111311222112132113213221133122211311221122111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321132132211322132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331222113321112131122211332113221122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213122112311311123112112322211322311311222113111231133211121312211231131112311211232221121113122113121113222123211211131221132211131221121321131211132221123113112211121312211231131122113221122112133221121321132132211331121321231231121113121113122122311311222113111231133221121113122113121113221112131221123113111231121123222112132113213221133112132123123112111312211322311211133112111312211213211311123113223112111321322123122113222122211211232221121113122113121113222123211211131211121311121321123113213221121113122123211211131221121311121312211213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121113222112131112131221121321131211132221121321132132211331121321232221123113112221131112311322311211131122211213211331121321122112133221121113122113121113222123112221221321132132211231131122211331121321232221121113122113121113222123211211131211121332211213111213122112132113121113222112132113213221232112111312111213322112132113213221133112132123123112111311222112132113311213211221121332211231131122211311123113321112131221123113112221132231131122211211131221131112311332211213211321223112111311222112132113212221132221222112112322211211131221131211132221232112111312111213111213211231131112311311221122132113213221133112132123222112311311222113111231132231121113112221121321133112132112211213322112111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121311121312211213211312111322211213211321322123211211131211121332211213211321322113311213211322132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113111231133221121321132122311211131122211213211321222113222122211211232221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213213211221113122113121113222112132113213221232112111312111213322112132113213221133112132123123112111312211322311211133112111312212221121123222112132113213221133112132123222113223113112221131112311332111213122112311311123112112322211211131221131211132221232112111312111213111213211231132132211211131221131211221321123113213221123113112221131112211322212322211231131122211322111312211312111322211213211321322113311213211331121113122122211211132213211231131122212322211331222113112211
132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113212231121113112221121321132132211231232112311321322112311311222113111231133221121113122113121113221112131221123113111231121123222112132113213221133122112231131122211211131221131112311332211213211321322113311213212322211231232112311321322112311311222113311213212322211231131122211311123113321112131221123113111231121123222112111312211312111322212321121113122113221113122112132113121113222112311311221112131221123113112211322112211213322112132113213221133112132123123112111312111312212231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113311213212312311211131122211213211331121321122112133221123123211231132132211231131122211331121321232221123113112221131112311322311211131122211213211331121321122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112211322112211213322112111312211312111322212321121113121112131112132112311321322112111312211312111322211322111312211312111322211213211321322123211211131211121332211231131122211311122122111312211213211312111322211231131122211311122113222123122113222122211211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113111231133221121321132122311211131122211213211321322112312321123113213221123113112221131112311332211211131221131211221321123113213221121113122113121113222123113221132122212231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122113221122112133221121113122113121113222123211211131211121311121321123113213221121113122113121113222113221113122113121113222112132113213221232112111312111213322112311311222113111221221113122112132113121113222112311311222113111221132221231221132221222112112322211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211132221121311121312211213211312111322211213211321322113311213212322211231131122211311123113223112111311222112132113311213211221121332211211131221131211132221231122212213211321322112311311222113311213212322211211131221131211132221231132212312311211132132212312211322212221121123222112132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113212231121113112221121321132132211231232112311321322112311311222113111231133221121113122113121113221112131221123113111231121123222112132113213221133112132123123112111311222112132113311213211221121332211322132113213221133112132123123112111311222112132113311213211221121332211231131122211311123113321112131221123113112221132231131122211211131221131112311332211213211321223112111311222112132113212221132221222112112322211211131221131211132221232112111312111213111213211231131112311311221122132113213221133112132123222112311311222113111231132231121113112221121321133112132112211213322112111312211312111322212321121113121112131112132112311311222113221321123123211231131122211211131221133112132113221321123113121113221112131122211332113221122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112311332211211133112111311222112111312211311123113322112111312211312111322212321121113121112133221121321132132211331121321132213211231132132211211131221232112111312212221121123222112311311222113111231133211121321321122111312211312111322211213211321322123211211131211121332211231131122211311123113321112131221123113111231121123222112111331121113112221121113122113111231133221121113122113121113221112131221123113111231121123222112111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321132132211322132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211231131122211311123113321112131221123113111231121113311211131221121321133112132113212221221113122113121113222123211211131211121332211213211321322113311213211322132112311321322112111312212321121113122122211211232221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112211322112211213322112111331121113112221121113122113111231133221121113122113121113221112131221123113111231121123222112111312211312111322212321121113122113221113122112132113121113222112311311221112131221123113112211322112211213322112111312211312111322212321121113121112131112132112311321322112111312212321121113122112131112131221121321132132211231131122211331121321232221121113122113121122132112311321322112111312211312113221133211322112211213322112132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113212231121113112221121321132132211231232112311321322112311311222113111231133221121113122113121113221112131221123113111231121123222112132113213221133112132123123112111312111312212231131122211311123113322112111312211312111322111213122112311311123112112322211211131221131211132221232112111312111213111213211231131122211322132112312321123113112211322112211213322112111312211312111322212321121113121112133221132213211321322113311213212312311211131122211213211331121321122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311222113111221221113122112132113121113222112132113213221133122211332111213322112132113213221132231131122211311123113322112111312211312111322212321121113122123211231131122113221123113221113122112132113213211121332212311322113212221
11131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211132221121311121312211213211312111322211213211321322113311213212322211231131122211311123113223112111311222112132113311213211221121332211211131221131211132221231122212213211321322112311311222113311213212322211211131221131211132221232112111312111213322112131112131221121321131211132221121321132132212321121113121112133221121321132132211331121321231231121113112221121321133112132112211213322112311311222113111231133211121312211231131122211322311311222112111312211311123113322112132113212231121113112221121321132122211322212221121123222112111312211312111322212321121113121112131112132112311311123113112211221321132132211331121321232221123113112221131112311322311211131122211213211331121321122112133221121113122113121113222123211211131211121311121321123113213221121113122123211211131221222112112322211213111213122112132113121113222112132113213221232112111312111213322112132113213221133112132113221321123113213221121113122123211211131221222112112322211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113212221132221222112112322211231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112221131112311332211322311311222113111231133221121113122113121113221112131221123113111231121123222112132113213221133122112231131122211211131221131112311332211213211321322113312221133211121311222113321132211221121332211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211132221121311121312211213211312111322211213211321322113311213212322211231131122211311122122111312211213211312111322211231131122211311123113321112132113222113121132112213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113212221132221222112112322211231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112221131112311332211322311311222113111231133221121113122113121113221112131221123113111231121123222112132113213221133122112231131122211211131221131112311332211213211321322113312221133211121311222113321132211221121332211231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122211211133112111311222112111312211312111322211213211321322123211211131211121332211231131122211311122122111312211213211312111322211231131122211311123113322112111331121113112221121113122113111231133221121113122113121113222123211211131211121332211213211321322113311213211322132112311321322112111312212321121113122122211211232221123113112221131112311332111213213211221113122113121113222112132113213221232112111312111213322112311311222113111231133211121321132211121311121321123113121113221112131122211332113221122112133221121113122113121113222123211211131211121311121321123113213221121113122123211211131221121311121312211213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121113222112131112131221121321131211132221121321132132211331121321232221123113112221131112311322311211131122211213211331121321122112133221121113122113121113222123211211131211121311121321123113213221121113122123211211131221222112112322211322111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321132132211322132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211231131122211311123113321112131221123113111231121113311211131221121321133112132113212221221113122113121113222123211211131211121332211213211321322113311213211322132112311321322112111312212321121113122122211211232221123113112221131112311332111213122112311311123112111331121113122112132113213221132211131221121311121312211213211321322112311311222123211211131221132211131221121321131112311322311211132132212312211322212221121123222112132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113212231121113112221121321132132211231232112311321322112311311222113111231133221121113122113121113221112131221123113111231121123222112132113213221133122112231131122211211131221131112311332211213211321322113311213212322211231232112311321322112311311222113311213212322211231131122211311123113321112131221123113111231121123222112111312211312111322212321121113122113221113122112132113121113222112311311221112131221123113112211322112211213322112132113213221133112132123123112111312111312212231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113311213212312311211131122211213211331121321122112133221123123211231132132211231131122211331121321232221123113112221131112311322311211131122211213211331121321122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112211322112211213322112111312211312111322212321121113121112131112132112311321322112111312211312111322211322111312211312111322211213211321322123211211131211121332211231131122211311122122111312211213211312111322211231131122211311122113222123122113222122211211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122123211211131221131211321122311311222113111231133211121312211231131112311211232221121113122113121113222123211211131221132211131221121321131211132221123113112211121312211231131122113221122112133221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113111231133221121321132122311211131122211213211321222113222122211211232221123123211231132132211231131122211331121321232221123113112221131112311322311211131122211213211331121321122112133221123113112221131112311332111213122112311311222113223113112221121113122113111231133221121321132122311211131122211213211321222113222122211211232221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112211322212312211322212221121123222112111312211312111322212321121113121112131112132112311321322112111312212321121113122112131112131221121321132132211231131122211331121321232221121113122113121122132112311321322112111312211312111322211213111213122112132113121113222112132113213221133112132123222112311311222113111231132231121113112221121321133112132112211213322112111312211312111322212321121113121112131112132112311311123113112211221321132132211331121321232221123113112221131112311322311211131122211213211331121321122112133221123113112221131112311332111213122112311311123112111331121113122112132113213221132211131221121311121312211213211321222113222122211211232221123113112221131112311332111213122112311311123112112322211322111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113111231133221121321132132211331221122311311222112111312211311123113322112111312211312111322212311322123123112112322211211131221131211132221132213211321322113311213212322211231131122211311123113321112131221123113112211121312211213211321222113222112132113223113112221121113122113121113123112112322111213211322211312113211
3113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112311332211211133112111311222112111312211311123113322112111312211312111322212321121113121112133221121321132132211331121321132213211231132132211211131221232112111312212221121123222112311311222113111231133211121321321122111312211312111322211213211321322123211211131211121332211231131122211311123113321112131221123113111231121123222112111331121113112221121113122113111231133221121113122113121113221112131221123113111231121123222112111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321132132211322132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211231131122211311123113321112131221123113111231121113311211131221121321133112132113212221221113122113121113222123211211131211121332211213211321322113311213211322132112311321322112111312212321121113122122211211232221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112211322112211213322112111331121113112221121113122113111231133221121113122113121113221112131221123113111231121123222112111312211312111322212321121113122113221113122112132113121113222112311311221112131221123113112211322112211213322112111312211312111322212321121113121112131112132112311321322112111312212321121113122112131112131221121321132132211231131122211331121321232221121113122113121122132112311321322112111312211312113221133211322112211213322112132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113213221133112132123222113221321132132211331121321232221123113112221131112311322311211131122211213211331121321122112133221121113122113121113222123112221221321132132211231131122211331121321232221121113122113121113222123113221231231121113213221231221132221222112112322211231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122211211133112111311222112111312211312111322211213211321322123211211131211121332211231131122211311122122111312211213211312111322211231131122211311123113322112111331121113112221121113122113111231133221121113122113121113222123211211131211121332211213211321322113312211223113112221121113122113111231133221121321132132211331121321231231121113122113322113111221131221221113122113121113222123211211131211121311121321123113213221121113122123211211131221121311121312211213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121132211332113221122112133221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113111231133221121321132132211331121321232221132213211321322113311213212322211231131122211311123113223112111311222112132113311213211221121332211211131221131211132221231122212213211321322112311311222113311213212322211211131221131211132221231132212312311211132132212312211322212221121123222112132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113212231121113112221121321132132211231232112311321322112311311222113111231133221121113122113121113221112131221123113111231121123222112132113213221133122112231131122211211131221131112311332211213211321322113311213212322211231232112311321322112311311222113311213212322211231131122211311123113321112131221123113111231121123222112111312211312111322212321121113122113221113122112132113121113222112311311221112131221123113112211322112211213322112132113213221133112132123123112111312111312212231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113311213212312311211131221132231121113311211131221121321131112311322311211132132212312211322212221121123222112311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122111213122112311311222112111331121113112221121113122113121113222112132113213221232112111312111213322112311311222113111221221113122112132113121113222112311311222113111231133221121113311211131122211211131221131112311332211211131221131211132221232112111312111213322112132113213221133112132113221321123113213221121113122123211211131221222112112322211231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122113221122112133221132231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122113221122112133221121113122113121113222123211211131211121311121321123113213221121113122113121113222113221113122113121113222112132113213221232112111312111213322112311311222113111221221113122112132113121113222112311311222113111221132221231221132221222112112322211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221232112111312211312113211223113112221131112311332111213122112311311123112112322211211131221131211132221232112111312211322111312211213211312111322211231131122111213122112311311221132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131211132221132231131122211211133112111311222112111312211312111322211213211321321112131221123113112221132231131122211211131221133112132113221321123113121113221112131122211332113221122112133221121113122113121113222123211211131211121311121321123113213221121113122123211211131221121311121312211213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121113222112131112131221121321131211132221121321132132211331121321232221123113112221131112311322311211131122211213211331121321122112133221121113122113121113222123112221221321132132211231131122211331121321232221121113122113121113222123211211131211121332211213111213122112132113121113222112132113213221232112111312111213322112132113213221133112132123123112111311222112132113311213211221121332211231131122211311123113321112131221123113112221132231131122211211131221131112311332211213211321223112111311222112132113212221132221222112112322211211131221131211132221232112111312111213111213211231131112311311221122132113213221133112132123222112311311222113111231132231121113112221121321133112132112211213322112111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121311121312211213211312111322211213211321322123211211131211121332211213211321322113311213211322132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113111231133221121321132122311211131122211213211321222113222122211211232221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311222113111231133221132231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331222113321112131122211332113221122112133221121113122113121113222123211211131211121311121321123113213221121113122123211211131221121311121312211213211321322112311311221112131221123113112221131112211312212213211321322113311213212312311211131122211213211331121321122112133221123113112221131112311332111213122112311311222113223113112221121113122113111231133221121321132122311211131122211213211321222113222122211211232221121113122113121113222123211211131211121311121321123113213221121113122123211211131221121311121312211213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121132211332113221122112133221121311121312211213211312111322211213211321322123211211131211121332211213211321322113311213211322132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321132132211322132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331222113321112131122211332113221122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112311332211211133112111311222112111312211311123113322112111312211312111322212321121113121112133221121321132132211331121321132213211231132132211211131221232112111312212221121123222112311311222113111231133211121312211231131112311211133112111312211213211331121321132122212211131221131211132221232112111312111213322112132113213221133112132113221321123113213221121113122123211211131221222112112322211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131211132221132231131122211211133112111311222112111312211312113221133211322112211213322112132113213221133112132123123112111311222112132113311213211221121332211322311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122111213122112311311221132211221121332211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312111322212311222122132113213221123113112221133112132123222112311311222113111231133211121321132211121311121321122112133221123113112221131112311332211322111312211312111322212321121113121112133221121321132132211331121321231231121113112221121321132122311211131122211211131221131211322113322112111312211322132113213221123113112221131112311311121321122112132231121113122113322113111221131221
13211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331121321232221123123211231132132211231131122211331121321232221123113112221131112311332111213122112311311123112112322211211131221131211132221232112111312211322111312211213211312111322211231131122111213122112311311221132211221121332211213211321322113311213212312311211131211131221223113112221131112311332211211131221131211132211121312211231131112311211232221121321132132211331121321231231121113112221121321133112132112211213322112312321123113213221123113112221133112132123222112311311222113111231132231121113112221121321133112132112211213322112311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122111213122112311311221132211221121332211211131221131211132221232112111312111213111213211231132132211211131221131211132221132211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112211322212312211322212221121123222112132113213221133112132123123112111311222112132113311213211231232112311311222112111312212321121113122113121132112231131122211311123113321112131221123113111231121123222112111312211312111322212321121113122113221113122112132113121113222112311311221112131221123113112211322112211213322112132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113212231121113112221121321132122211322212221121123222112312321123113213221123113112221133112132123222112311311222113111231132231121113112221121321133112132112211213322112311311222113111231133211121312211231131122211322311311222112111312211311123113322112132113212231121113112221121321132122211322212221121123222112311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122111213122112311311222112111331121113112221121113122113121113222112132113213221232112111312111213322112311311222113111221221113122112132113121113222112311311222113111221132221231221132221222112112322211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312111322212321121113121112133221132211131221131211132221232112111312111213322112132113213221133112132113221321123113213221121113122123211211131221222112112322211231131122211311123113321112132132112211131221131211132221121321132132212321121113121112133221123113112221131112311332111213211322111213111213211231131211132211121311222113321132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331121321232221123123211231132132211231131122211331121321232221123113112221131112311332111213122112311311123112112322211211131221131211132221231122212213211321322112311311222113311213212322211211131221131211132221232112111312111213111213211231131122212322211331222113112211223113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112211322212312211322212221121123222112111312211312111322212321121113121112131112132112311321322112111312212321121113122112131112131221121321132132211231131122211331121321232221121113122113121113222123211211131211121332211322111312211312111322212321121113121112133221121321132132211331121321132213211231132132211211131221232112111312212221121123222112311311222113111231133211121321321122111312211312111322211213211321322123211211131211121332211231131122211311123113321112132113221112131112132112311312111322111213112221133211322112211213322112111312211312111322212321121113121112131112132112311321322112111312212321121113122112131112131221121321132132211231131122211331121321232221121113122113121122132112311321322112111312211312111322211213111213122112132113121113222112132113213221133112132123222112311311222113111231132231121113112221121321133112132112211213322112111312211312111322212311222122132113213221123113112221133112132123222112111312211312111322212321121113121112133221121311121312211213211312111322211213211321322123211211131211121332211213211321322113311213212312311211131122211213211331121321122112133221123113112221131112311332111213122112311311222113223113112221121113122113111231133221121321132122311211131122211213211321222113222122211211232221121113122113121113222123211211131211121311121321123113111231131122112213211321322113311213212322211231131122211311123113223112111311222112132113311213211221121332211211131221131211132221232112111312111213111213211231131122211322132112312321123113112221121113122113311213211322132112311312111322111213112221133211322112211213322112132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113212231121113112221121321132132211231232112311321322112311311222113111231133221121113122113121113221112131221123113111231121123222112132113213221133122112231131122211211131221131112311332211213211321322113311213212322211231232112311321322112311311222113311213212322211231131122211311123113321112131221123113111231121123222112111312211312111322212321121113122113221113122112132113121113222112311311221112131221123113112211322112211213322112132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113212231121113112221121321132122211322212221121123222113221321132132211331121321231231121113112221121321133112132112312321123113112221121113122113111231133221121321132122311211131122211213211321222113222122211211232221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311222113111231133221132231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331222113321112131122211332113221122112133221121113122113121113222123211211131211121311121321123113213221121113122123211211131221121311121312211213211321322112311311221112131221123113112221131112211312212213211321322113311213212312311211131122211213211331121321122112133221123113112221131112311332111213122112311311222113223113112221121113122113111231133221121321132122311211131122211213211321222113222122211211232221121113122113121113222123211211131211121311121321123113213221121113122123211211131221121311121312211213211321322112311311222113111231133221132213211321322112312321123113213221123113112221131112311332211211131221131211131231121113112221121321132132211322132113213221123113112221232112111312211322111312211213211311123113223112111321322123122113222122211211232221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112311332211211133112111311222112111312211311123113322112111312211312111322212321121113121112133221121321132132211331121321132213211231132132211211131221232112111312212221121123222112311311222113111231133211121321321122111312211312111322211213211321322123211211131211121332211231131122211311123113321112131221123113111231121123222112111331121113112221121113122113111231133221121113122113121113221112131221123113111231121123222112111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321132132211322132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211231131122211311123113321112131221123113111231121113311211131221121321133112132113212221221113122113121113222123211211131211121332211213211321322113311213211322132112311321322112111312212321121113122122211211232221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112211322112211213322112111331121113112221121113122113111231133221121113122113121113221112131221123113111231121123222112111312211312111322212321121113122113221113122112132113121113222112311311221112131221123113112211322112211213322112111312211312111322212321121113121112131112132112311321322112111312212321121113122112131112131221121321132132211231131122211331121321232221121113122113121122132112311321322112111312211312113221133211322112211213322112132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113213221133112132123222113221321132132211331121321232221123113112221131112311322311211131122211213211331121321122112133221121113122113121113222123112221221321132132211231131122211331121321232221121113122113121113222123113221231231121113213221231221132221222112112322211231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122211211133112111311222112111312211312111322211213211321223112111311222112132113213221133122211311221122111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321132132211322132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122211211133112111311222112111312211312111322211213211321322123211211131211121332211231131122211311122122111312211213211312111322211231131122211311122113222123122113222122211211232221121113311211131122211211131221131112311332211211131221131211132211121312211231131112311211232221121113122113121113222123211211131221132211131221121321131211132221123113112211121312211231131122113221122112133221121113122113121113222123211211131211121311121321123113213221121113122113121113222113221113122113121113222112132113213221232112111312111213322112311311222113111221221113122112132113121113222112311311222113111221132221231221132221222112112322211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211132221121311121312211213211312111322211213211321322113311213212322211231131122211311123113223112111311222112132113311213211221121332211211131221131211132221231122212213211321322112311311222113311213212322211211131221131211132221231132212312311211132132212312211322212221121123222112132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113212231121113112221121321132132211231232112311321322112311311222113111231133221121113122113121113221112131221123113111231121123222112132113213221133122112231131122211211131221131112311332211213211321322113311213212322211231232112311321322112311311222113311213212322211231131122211311123113321112131221123113111231121123222112111312211312111322212321121113122113221113122112132113121113222112311311221112131221123113112211322112211213322112132113213221133112132123123112111311222112132113311213211231232112311311222112111312212321121113122113121132112231131122211311123113321112131221123113111231121123222112111312211312111322212321121113122113221113122112132113121113222112311311221112131221123113112211322112211213322112111312211312111322212321121113121112131112132112311321322112111312212321121113122112131112131221121321132132211231131122211311123113322113221321132132211231232112311321322112311311222113111221132221231221132221222112112322211211131221131211132221232112111312111213111213211231132132211211131221232112111312212221121123222113221321132132211331121321231231121113112221121321133112132112312321123113112221121113122113111231133221121321132122311211131122211213211321222113222122211211232221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213213211221113122113121113222112132113213221232112111312111213322112132113213221133112132123123112111312211322311211133112111312212221121123222112132113213221133112132123222113223113112221131112311332111213122112311311123112112322211211131221131211132221232112111312111213111213211231132132211211131221131211221321123113213221123113112221131112211322212322211231131122211322111312211312111322211213211321322113311213211331121113122122211211132213211231131122212322211331222113112211
1113122113121113222123211211131211121311121321123113213221121113122123211211131221121311121312211213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121113222112131112131221121321131211132221121321132132211331121321232221123113112221131112311322311211131122211213211331121321122112133221121113122113121113222123112221221321132132211231131122211331121321232221121113122113121113222123211211131211121332211213111213122112132113121113222112132113213221232112111312111213322112132113213221133112132123123112111311222112132113311213211221121332211231131122211311123113321112131221123113112221132231131122211211131221131112311332211213211321223112111311222112132113212221132221222112112322211211131221131211132221232112111312111213111213211231131112311311221122132113213221133112132123222112311311222113111231132231121113112221121321133112132112211213322112111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121311121312211213211312111322211213211321322123211211131211121332211213211321322113311213211322132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113111231133221121321132122311211131122211213211321222113222122211211232221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311222113111231133221132231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331222113321112131122211332113221122112133221121113122113121113222123211211131211121311121321123113213221121113122123211211131221121311121312211213211321322112311311221112131221123113112221131112211312212213211321322113311213212312311211131122211213211331121321122112133221123113112221131112311332111213122112311311222113223113112221121113122113111231133221121321132122311211131122211213211321222113222122211211232221121113122113121113222123211211131211121311121321123113213221121113122123211211131221121311121312211213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121132211332113221122112133221121311121312211213211312111322211213211321322123211211131211121332211213211321322113311213211322132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321132132211322132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331222113321112131122211332113221122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213122112311311123112112322211322311311222113111231133211121312211231131112311211232221121113122113121113222123211211131221132211131221121321131211132221123113112211121312211231131122113221122112133221121321132132211331121321231231121113121113122122311311222113111231133221121113122113121113221112131221123113111231121123222112132113213221133112132123123112111312211322311211133112111312211213211311123113223112111321322123122113222122211211232221121113122113121113222123211211131211121311121321123113213221121113122123211211131221121311121312211213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121113222112131112131221121321131211132221121321132132211331121321232221123113112221131112311322311211131122211213211331121321122112133221121113122113121113222123112221221321132132211231131122211331121321232221121113122113121113222123211211131211121332211213111213122112132113121113222112132113213221232112111312111213322112132113213221133112132123123112111311222112132113311213211221121332211231131122211311123113321112132132112211131221131211132221121321132132212321121113121112133221123113112221131112311332111213122112311311123112111331121113122112132113213211121332212311322113212221221321132132211331121321231231121113112221121321133112132112312321123113112221121113122113111231133221121321132122311211131122211213211321322112312321123113213221123113112221131112311332211211131221131211132211121312211231131112311211232221121321132132211331221122311311222112111312211311123113322112132113213221133122211332111213112221133211322112211213322112311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122111213122112311311222112111331121113112221121113122113121113222112132113213221232112111312111213322112311311222113111231133211121312211231131112311211232221132231131122211311123113321112131221123113111231121123222112111312211312111322212321121113122113221113122112132113121113222112311311221112131221123113112211322112211213322112132113213221133112132123123112111312111312212231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113311213212312311211131221132231121113311211131221121321131112311322311211132132212312211322212221121123222112311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122111213122112311311222112111331121113112221121113122113121113222112132113213221232112111312111213322112311311222113111221221113122112132113121113222112311311222113111231133221121113311211131122211211131221131112311332211211131221131211132221232112111312111213322112132113213221133112132113221321123113213221121113122123211211131221222112112322211231131122211311123113321112132132112211131221131211132221121321132132212321121113121112133221123113112221131112311332111213122112311311123112112322211211133112111311222112111312211311123113322112111312211312111322111213122112311311123112112322211211131221131211132221232112111312111213111213211231132132211211131221232112111312212221121123222112132113213221133112132123123112111311222112132113213221132213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121132211332113221122112133221123113112221131112311332111213122112311311123112111331121113122112132113311213211321222122111312211312111322212321121113121112133221121321132132211331121321132213211231132132211211131221232112111312212221121123222112311311222113111231133211121312211231131112311211133112111312211213211321322113221113122112131112131221121321132132211231131122212321121113122113221113122112132113111231132231121113213221231221132221222112112322211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211132221121311121312211213211312111322211213211321322113311213212322211231131122211311123113223112111311222112132113311213211221121332211211131221131211132221231122212213211321322112311311222113311213212322211211131221131211132221232112111312111213322112131112131221121321131211132221121321132132212321121113121112133221121321132132211331121321231231121113112221121321133112132112211213322112311311222113111231133211121312211231131122211322311311222112111312211311123113322112132113212231121113112221121321132122211322212221121123222112111312211312111322212321121113121112131112132112311321322112111312212321121113122112131112131221121321132132211231131122211331121321232221121113122113121122132112311321322112111312211312113221133211322112211213322113221113122113121113222123211211131211121311121321123113213221121113122123211211131221121311121312211213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121132211332113221122112133221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113111231133221121321132132211331121321232221132213211321322113311213212322211231131122211311123113223112111311222112132113311213211221121332211211131221131211132221231122212213211321322112311311222113311213212322211211131221131211132221231132212312311211132132212312211322212221121123222112311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122111213122112311311222112111331121113112221121113122113121113222112132113212231121113112221121321132132211331222113112211221113122113121113222123211211131211121311121321123113213221121113122123211211131221222112112322211213211321322113311213212312311211131122211213211321322113221321132132211231131122211331121321232221121113122113121122132112311321322112111312211312113221133211322112211213322112311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122111213122112311311222112111331121113112221121113122113121113222112132113213221133112132123222113221113122113121113222112131112131221121321131211132221121321132132211331121321232221123113112221131112311311121321123113213221121113122113121113222113221113122113121113222112132113213211121312211231131122211322311311222112111312211331121321132213211231131211132211121311222113321132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331121321232221123123211231132132211231131122211331121321232221123113112221131112311332111213122112311311123112112322211211131221131211132221232112111312211322111312211213211312111322211231131122111213122112311311221132211221121332211213211321322113311213212312311211131211131221223113112221131112311332211211131221131211132211121312211231131112311211232221121321132132211331121321231231121113112221121321133112132112211213322112312321123113213221123113112221133112132123222112311311222113111231132231121113112221121321133112132112211213322112311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122111213122112311311221132211221121332211211131221131211132221232112111312111213111213211231132132211211131221131211132221132211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112211322212312211322212221121123222112132113213221133112132123123112111311222112132113311213211231232112311311222112111312212321121113122113121132112231131122211311123113321112131221123113111231121123222112111312211312111322212321121113122113221113122112132113121113222112311311221112131221123113112211322112211213322112132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113212231121113112221121321132122211322212221121123222112312321123113213221123113112221133112132123222112311311222113111231132231121113112221121321133112132112211213322112311311222113111231133211121312211231131122211322311311222112111312211311123113322112132113212231121113112221121321132122211322212221121123222112311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122111213122112311311222112111331121113112221121113122113121113222112132113213221232112111312111213322112311311222113111221221113122112132113121113222112311311222113111221132221231221132221222112112322211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312111322212321121113121112133221132211131221131211132221232112111312111213322112132113213221133112132113221321123113213221121113122123211211131221222112112322211231131122211311123113321112132132112211131221131211132221121321132132212321121113121112133221123113112221131112311332111213211322111213111213211231131211132211121311222113321132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312112213211231132132211211131221131211132221231132211321222122311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122111213122112311311221132211221121332211211131221131211132221232112111312111213111213211231132132211211131221131211132221132211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112211322212312211322212221121123222112132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113212231121113112221121321132132211231232112311321322112311311222113111231133221121113122113121113221112131221123113111231121123222112132113213221133122112231131122211211131221131112311332211213211321322113312221133211121311222113321132211221121332211231232112311321322112311311222113311213212322211231131122211311123113223112111311222112132113311213211221121332211231131122211311123113321112131221123113112221132231131122211211131221131112311332211213211321223112111311222112132113212221132221222112112322211231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112221131112311332211322311311222113111231133221121113122113121113221112131221123113111231121123222112132113213221133122112231131122211211131221131112311332211213211321322113312221133211121311222113321132211221121332211231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122211211133112111311222112111312211312111322211213211321322123211211131211121332211231131122211311122122111312211213211312111322211231131122211311123113322112111331121113112221121113122113111231133221121113122113121113222123211211131211121332211213211321322113311213211322132112311321322112111312212321121113122122211211232221123113112221131112311332111213213211221113122113121113222112132113213221232112111312111213322112311311222113111231133211121321132211121311121321123113121113221112131122211332113221122112133221121113122113121113222123211211131211121311121321123113213221121113122123211211131221121311121312211213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121113222112131112131221121321131211132221121321132132211331121321232221123113112221131112311322311211131122211213211331121321122112133221121113122113121113222123112221221321132132211231131122211331121321232221121113122113121113222123211211131211121332211213111213122112132113121113222112132113213221232112111312111213322112132113213221133112132123123112111311222112132113311213211221121332211231131122211311123113321112131221123113112221132231131122211211131221131112311332211213211321223112111311222112132113212221132221222112112322211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112211121312211231131122211311122113122122132113213221133112132123123112111311222112132113311213211221121332211231131122211311123113321112131221123113112221132231131122211211131221131112311332211213211321223112111311222112132113212221132221222112112322211231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122211211133112111311222112111312211312111322211213211321322113311213212322211322111312211312111322211213111213122112132113121113222112132113213221133122211332111213112221133211322112211213322112311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122111213122112311311221132211221121332211322111312211312111322212321121113121112131112132112311321322112111312212321121113122112131112131221121321132132211231131122211331121321232221121113122113121122132112311321322112111312211312113221133211322112211213322112132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113212231121113112221121321132132211231232112311321322112311311222113111231133221121113122113121113221112131221123113111231121123222112132113213221133112132123123112111312111312212231131122211311123113322112111312211312111322111213122112311311123112112322211211131221131211132221232112111312111213111213211231131122211322132112312321123113112211322112211213322112111312211312111322212321121113121112133221132213211321322113311213212312311211131122211213211331121321122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311222113111221221113122112132113121113222112132113213221133122211332111213322112132113213221132231131122211311123113322112111312211312111322212321121113122123211231131122113221123113221113122112132113213211121332212311322113212221
31131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122211211133112111311222112111312211312111322211213211321322123211211131211121332211231131122211311122122111312211213211312111322211231131122211311123113322112111331121113112221121113122113111231133221121113122113121113222123211211131211121332211213211321322113311213211322132112311321322112111312212321121113122122211211232221123113112221131112311332111213213211221113122113121113222112132113213221232112111312111213322112311311222113111231133211121312211231131112311211232221121113311211131122211211131221131112311332211211131221131211132211121312211231131112311211232221121113122113121113222123211211131211121311121321123113213221121113122123211211131221222112112322211213211321322113311213212312311211131122211213211321322113221321132132211231131122211331121321232221121113122113121122132112311321322112111312211312113221133211322112211213322112311311222113111231133211121312211231131112311211133112111312211213211331121321132122212211131221131211132221232112111312111213322112132113213221133112132113221321123113213221121113122123211211131221222112112322211231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122113221122112133221121113311211131122211211131221131112311332211211131221131211132211121312211231131112311211232221121113122113121113222123211211131221132211131221121321131211132221123113112211121312211231131122113221122112133221121113122113121113222123211211131211121311121321123113213221121113122123211211131221121311121312211213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121132211332113221122112133221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113111231133221121321132132211331121321232221132213211321322113311213212322211231131122211311123113223112111311222112132113311213211221121332211211131221131211132221231122212213211321322112311311222113311213212322211211131221131211132221231132212312311211132132212312211322212221121123222112311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122111213122112311311222112111331121113112221121113122113121113222112132113212231121113112221121321132132211331222113112211221113122113121113222123211211131211121311121321123113213221121113122123211211131221222112112322211213211321322113311213212312311211131122211213211321322113221321132132211231131122211331121321232221121113122113121122132112311321322112111312211312113221133211322112211213322112311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122111213122112311311222112111331121113112221121113122113121113222112132113213221232112111312111213322112311311222113111221221113122112132113121113222112311311222113111221132221231221132221222112112322211211133112111311222112111312211311123113322112111312211312111322111213122112311311123112112322211211131221131211132221232112111312211322111312211213211312111322211231131122111213122112311311221132211221121332211211131221131211132221232112111312111213111213211231132132211211131221131211132221132211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112211322212312211322212221121123222112111312211312111322212321121113121112131112132112311321322112111312212321121113122112131112131221121321132132211231131122211331121321232221121113122113121122132112311321322112111312211312111322211213111213122112132113121113222112132113213221133112132123222112311311222113111231132231121113112221121321133112132112211213322112111312211312111322212311222122132113213221123113112221133112132123222112111312211312111322212311322123123112111321322123122113222122211211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113111231133221121321132122311211131122211213211321322112312321123113213221123113112221131112311332211211131221131211132211121312211231131112311211232221121321132132211331121321231231121113112221121321133112132112211213322113221321132132211331121321231231121113112221121321133112132112211213322112311311222113111231133211121312211231131122211322311311222112111312211311123113322112132113212231121113112221121321132122211322212221121123222112111312211312111322212321121113121112131112132112311311123113112211221321132132211331121321232221123113112221131112311322311211131122211213211331121321122112133221121113122113121113222123211211131211121311121321123113112221132213211231232112311311222112111312211331121321132213211231131211132211121311222113321132211221121332211231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122211211133112111311222112111312211312111322211213211321322123211211131211121332211231131122211311122122111312211213211312111322211231131122211311123113322112111331121113112221121113122113111231133221121113122113121113222123211211131211121332211213211321322113311213211322132112311321322112111312212321121113122122211211232221123113112221131112311332111213213211221113122113121113222112132113213221232112111312111213322112311311222113111231133211121312211231131112311211232221121113311211131122211211131221131112311332211211131221131211132211121312211231131112311211232221121113122113121113222123211211131211121311121321123113213221121113122123211211131221222112112322211213211321322113311213212312311211131211131221223113112221131112311332211211131221131211132211121312211231131112311211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113121113123112112322111213211322211312113211221113122113121113222123211211131211121311121321123113213221121113122123211211131221121311121312211213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121113222112131112131221121321131211132221121321132132211331121321232221123113112221131112311322311211131122211213211331121321122112133221121113122113121113222123112221221321132132211231131122211331121321232221121113122113121113222123113221231231121113213221231221132221222112112322211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113311213212312311211131122211213211331121321122112133221132213211321322113311213212312311211131122211213211331121321122112133221123113112221131112311332111213122112311311222113223113112221121113122113111231133221121321132122311211131122211213211321222113222122211211232221121113122113121113222123211211131211121311121321123113111231131122112213211321322113311213212322211231131122211311123113223112111311222112132113311213211221121332211211131221131211132221232112111312111213111213211231131122211322132112312321123113112221121113122113311213211322132112311312111322111213112221133211322112211213322112132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113212231121113112221121321132132211231232112311321322112311311222113111231133221121113122113121113221112131221123113111231121123222112132113213221133122112231131122211211131221131112311332211213211321322113311213212322211231232112311321322112311311222113311213212322211231131122211311123113321112131221123113111231121123222112111312211312111322212321121113122113221113122112132113121113222112311311221112131221123113112211322112211213322112132113213221133112132123123112111312111312212231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113311213212312311211131122211213211331121321122112133221123123211231132132211231131122211331121321232221123113112221131112311322311211131122211213211331121321122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112211322112211213322112111312211312111322212321121113121112131112132112311321322112111312211312111322211322111312211312111322211213211321322123211211131211121332211231131122211311122122111312211213211312111322211231131122211311122113222123122113222122211211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122123211211131221131211321122311311222113111231133211121312211231131112311211232221121113122113121113222123211211131221132211131221121321131211132221123113112211121312211231131122113221122112133221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113121113222113223113112221121113311211131122211211131221131211132221121321132132111213122112311311222113223113112221121113122113311213211322132112311312111322111213112221133211322112211213322112311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122111213122112311311222112111331121113112221121113122113121113222112132113213221232112111312111213322112311311222113111221221113122112132113121113222112311311222113111231133221121113311211131122211211131221131112311332211211131221131211132221232112111312111213322112132113213221133112132113221321123113213221121113122123211211131221222112112322211231131122211311123113321112132132112211131221131211132221121321132132212321121113121112133221123113112221131112311332111213122112311311123112112322211211133112111311222112111312211311123113322112111312211312111322111213122112311311123112112322211211131221131211132221232112111312111213111213211231132132211211131221232112111312212221121123222112132113213221133112132123123112111311222112132113213221132213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121132211332113221122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112211322212312211322212221121123222113223113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112211322212312211322212221121123222112111312211312111322212321121113121112131112132112311321322112111312212321121113122112131112131221121321132132211231131122211331121321232221121113122113121113222123211211131211121332211322111312211312111322212321121113121112133221121321132132211331121321132213211231132132211211131221232112111312212221121123222112311311222113111231133211121321321122111312211312111322211213211321322123211211131211121332211231131122211311123113321112132113221112131112132112311312111322111213112221133211322112211213322112132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113212231121113112221121321132132211231232112311321322112311311222113111231133221121113122113121122132112311321322112111312211312111322212311322113212221223113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112211322112211213322112111312211312111322212321121113121112131112132112311321322112111312211312111322211322111312211312111322211213211321322123211211131211121332211231131122211311122122111312211213211312111322211231131122211311122113222123122113222122211211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113111231133221121321132122311211131122211213211321322112312321123113213221123113112221131112311332211211131221131211132221232112111312111213322113223113112221131112311332211211133112111311222112111312211311123113322112111312211312111322212321121113121112133221121321132132211331121321133112111312211213211312111322211231131122211311123113322113223113112221131112311332211211131221131211131231121113112221121321132132211322132113213221123113112221232112111312211322111312211213211311123113223112111321322123122113222122211211232221121113122113121113222123211211131211121311121321123113213221121113122123211211131221121311121312211213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121113222112131112131221121321131211132221121321132132211331121321232221123113112221131112311322311211131122211213211331121321122112133221121113122113121113222123112221221321132132211231131122211331121321232221121113122113121113222123211211131211121332211213111213122112132113121113222112132113213221232112111312111213322112132113213221133112132123123112111311222112132113311213211221121332211231131122211311123113321112131221123113112221132231131122211211131221131112311332211213211321223112111311222112132113212221132221222112112322211211131221131211132221232112111312111213111213211231131112311311221122132113213221133112132123222112311311222113111231132231121113112221121321133112132112211213322112111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121311121312211213211312111322211213211321322123211211131211121332211213211321322113311213211322132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113111231133221121321132122311211131122211213211321222113222122211211232221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311222113111231133221132231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331222113321112131122211332113221122112133221121113122113121113222123211211131211121311121321123113213221121113122123211211131221121311121312211213211321322112311311221112131221123113112221131112211312212213211321322113311213212312311211131122211213211331121321122112133221123113112221131112311332111213122112311311222113223113112221121113122113111231133221121321132122311211131122211213211321222113222122211211232221121113122113121113222123211211131211121311121321123113213221121113122123211211131221121311121312211213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121132211332113221122112133221121311121312211213211312111322211213211321322123211211131211121332211213211321322113311213211322132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321132132211322132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331222113321112131122211332113221122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213122112311311123112112322211322311311222113111231133211121312211231131112311211232221121113122113121113222123211211131221132211131221121321131211132221123113112211121312211231131122113221122112133221121321132132211331121321231231121113121113122122311311222113111231133221121113122113121113221112131221123113111231121123222112132113213221133112132123123112111312211322311211133112111312211213211311123113223112111321322123122113222122211211232221121113122113121113222123211211131211121311121321123113213221121113122123211211131221121311121312211213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121113222112131112131221121321131211132221121321132132211331121321232221123113112221131112212211131221121321131211132221123113112221131112311332111213211322211312113211221321132132211331121321231231121113112221121321133112132112312321123113112221121113122113111231133221121321132122311211131122211213211321222113222122211211232221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311222113111231133221132231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331222113321112131122211332113221122112133221121113122113121113222123211211131211121311121321123113213221121113122123211211131221121311121312211213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121113222112131112131221121321131211132221121321132132211331121321232221123113112221131112311322311211131122211213211331121321122112133221121113122113121113222123112221221321132132211231131122211331121321232221121113122113121113222123113221231231121113213221231221132221222112112322211213111213122112132113121113222112132113213221232112111312111213322112132113213221133112132113221321123113213221121113122123211211131221222112112322211213211321322113311213212312311211131122211213211321322113221321132132211231131122211331121321232221121113122113121122132112311321322112111312211312113221133211322112211213322112132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113213221133112132123222113221321132132211331121321232221123113112221131112311322311211131122211213211331121321122112133221121113122113121113222123112221221321132132211231131122211331121321232221121113122113121113222123113221231231121113213221231221132221222112112322211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331121321232221123123211231132132211231131122211331121321232221123113112221131112311332111213122112311311123112112322211211131221131211132221232112111312211322111312211213211312111322211231131122111213122112311311221132211221121332211213211321322113311213212312311211131211131221223113112221131112311332211211131221131211132211121312211231131112311211232221121321132132211331121321231231121113122113223112111331121113122112132113111231132231121113213221231221132221222112112322211231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122211211133112111311222112111312211312111322211213211321322123211211131211121332211231131122211311122122111312211213211312111322211231131122211311123113322112111331121113112221121113122113111231133221121113122113121113222123211211131211121332211213211321322113311213211322132112311321322112111312212321121113122122211211232221123113112221131112311332111213213211221113122113121113222112132113213221232112111312111213322112311311222113111231133211121312211231131112311211232221121113311211131122211211131221131112311332211211131221131211132211121312211231131112311211232221121113122113121113222123211211131211121311121321123113213221121113122123211211131221222112112322211213211321322113311213212312311211131122211213211321322113221321132132211231131122211331121321232221121113122113121122132112311321322112111312211312113221133211322112211213322112311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122111213122112311311222112111331121113112221121113122113121113222112132113212231121113112221121321132132211331222113112211221113122113121113222123211211131211121311121321123113213221121113122123211211131221222112112322211213211321322113311213212312311211131122211213211321322113221321132132211231131122211331121321232221121113122113121122132112311321322112111312211312113221133211322112211213322112132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113212231121113112221121321132132211231232112311321322112311311222113111231133221121113122113121113222123211211131211121332211322311311222113111231133221121113311211131122211211131221131112311332211211131221131211132221231132212312311211132132212312211322212221121123222112132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113212231121113112221121321132122211322212221121123222113223113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112211322212312211322212221121123222112111312211312111322212321121113121112131112132112311321322112111312212321121113122112131112131221121321132132211231131122211331121321232221121113122113121122132112311321322112111312211312111322211213111213122112132113121113222112132113213221133112132123222112311311222113111231132231121113112221121321133112132112211213322112111312211312111322212321121113121112131112132112311311123113112211221321132132211331121321232221123113112221131112311322311211131122211213211331121321122112133221123113112221131112311332111213122112311311123112111331121113122112132113213221132211131221121311121312211213211321222113222122211211232221123113112221131112311332111213122112311311123112112322211322111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113111231133221121321132132211331221122311311222112111312211311123113322112111312211312111322212311322123123112112322211211131221131211132221132213211321322113311213212322211231131122211311123113321112131221123113112211121312211213211321222113222112132113223113112221121113122113121113123112112322111213211322211312113211
1321132132211331121321231231121113112221121321133112132112312321123113112221121113122113111231133221121321132122311211131122211213211321322112312321123113213221123113112221131112311332211211131221131211132211121312211231131112311211232221121321132132211331221122311311222112111312211311123113322112132113213221133112132123222112312321123113213221123113112221133112132123222112311311222113111231133211121312211231131112311211232221121113122113121113222123211211131221132211131221121321131211132221123113112211121312211231131122113221122112133221121321132132211331121321231231121113121113122122311311222113111231133221121113122113121113221112131221123113111231121123222112132113213221133112132123123112111311222112132113311213211221121332211231232112311321322112311311222113311213212322211231131122211311123113223112111311222112132113311213211221121332211231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122113221122112133221121113122113121113222123211211131211121311121321123113213221121113122113121113222113221113122113121113222112132113213221232112111312111213322112311311222113111221221113122112132113121113222112311311222113111221132221231221132221222112112322211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221232112111312211312113211223113112221131112311332111213122112311311123112112322211211131221131211132221232112111312211322111312211213211312111322211231131122111213122112311311221132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113212221132221222112112322211231232112311321322112311311222113311213212322211231131122211311123113223112111311222112132113311213211221121332211231131122211311123113321112131221123113112221132231131122211211131221131112311332211213211321223112111311222112132113212221132221222112112322211231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122211211133112111311222112111312211312111322211213211321322123211211131211121332211231131122211311122122111312211213211312111322211231131122211311122113222123122113222122211211232221121113122113121113222123211211131211121311121321123113213221121113122123211211131221121311121312211213211321322112311311222113311213212322211211131221131211132221232112111312111213322113221113122113121113222123211211131211121332211213211321322113311213211322132112311321322112111312212321121113122122211211232221123113112221131112311332111213213211221113122113121113222112132113213221232112111312111213322112311311222113111231133211121321132211121311121321123113121113221112131122211332113221122112133221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113111231133221121321132122311211131122211213211321322112312321123113213221123113112221131112311332211211131221131211221321123113213221121113122113121113222123113221132122212231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122113221122112133221121113122113121113222123211211131211121311121321123113213221121113122113121113222113221113122113121113222112132113213221232112111312111213322112311311222113111221221113122112132113121113222112311311222113111221132221231221132221222112112322211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331222113321112131122211332113221122112133221123123211231132132211231131122211331121321232221123113112221131112311322311211131122211213211331121321122112133221123113112221131112311332111213122112311311222113223113112221121113122113111231133221121321132122311211131122211213211321222113222122211211232221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311222113111231133221132231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331222113321112131122211332113221122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112311332211211133112111311222112111312211311123113322112111312211312111322212321121113121112133221121321132132211331121321132213211231132132211211131221232112111312212221121123222112311311222113111231133211121321321122111312211312111322211213211321322123211211131211121332211231131122211311123113321112132113221112131112132112311312111322111213112221133211322112211213322112111312211312111322212321121113121112131112132112311321322112111312212321121113122112131112131221121321132132211231131122211331121321232221121113122113121122132112311321322112111312211312111322211213111213122112132113121113222112132113213221133112132123222112311311222113111231132231121113112221121321133112132112211213322112111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221132211131221131211132221232112111312111213111213211231132132211211131221232112111312212221121123222112132113213221133112132123123112111311222112132113213221132213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121132211332113221122112133221123113112221131112311332111213122112311311123112111331121113122112132113311213211321222122111312211312111322212321121113121112133221121321132132211331121321132213211231132132211211131221232112111312212221121123222112311311222113111231133211121312211231131112311211133112111312211213211321322113221113122112131112131221121321132132211231131122212321121113122113221113122112132113111231132231121113213221231221132221222112112322211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331121321232221123123211231132132211231131122211331121321232221123113112221131112311332111213122112311311123112112322211211131221131211132221232112111312211322111312211213211312111322211231131122111213122112311311221132211221121332211213211321322113311213212312311211131211131221223113112221131112311332211211131221131211132211121312211231131112311211232221121321132132211331121321231231121113112221121321133112132112211213322112312321123113213221123113112221133112132123222112311311222113111231132231121113112221121321133112132112211213322112311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122111213122112311311221132211221121332211211131221131211132221232112111312111213111213211231131112311311221122132113213221133112132123222112311311222113111231132231121113112221121321133112132112211213322112111312211312111322212321121113121112131112132112311321322112111312212321121113122112131112131221121321132132211231131122211311123113111213211221121322311211131221133221131112211312212231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122211211133112111311222112111312211312111322211213211321322123211211131211121332211231131122211311122122111312211213211312111322211231131122211311123113322112111331121113112221121113122113111231133221121113122113121113222123211211131211121332211213211321322113311213211322132112311321322112111312212321121113122122211211232221123113112221131112311332111213213211221113122113121113222112132113213221232112111312111213322112311311222113111231133211121321132211121311121321123113121113221112131122211332113221122112133221121113122113121113222123211211131211121311121321123113213221121113122123211211131221121311121312211213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121113222112131112131221121321131211132221121321132132211331121321232221123113112221131112311322311211131122211213211331121321122112133221121113122113121113222123211211131211121311121321123113213221121113122123211211131221222112112322211322111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321132132211322132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211231131122211311123113321112131221123113111231121113311211131221121321133112132113212221221113122113121113222123211211131211121332211213211321322113311213211322132112311321322112111312212321121113122122211211232221123113112221131112311332111213122112311311123112111331121113122112132113213221132211131221121311121312211213211321322112311311222123211211131221132211131221121321131112311322311211132132212312211322212221121123222112111312211312111322212321121113121112131112132112311321322112111312212321121113122112131112131221121321132132211231131122211331121321232221121113122113121122132112311321322112111312211312111322211213111213122112132113121113222112132113213221133112132123222112311311222113111231132231121113112221121321133112132112211213322112111312211312111322212311222122132113213221123113112221133112132123222112111312211312111322212321121113121112133221121311121312211213211312111322211213211321322123211211131211121332211213211321322113311213212312311211131122211213211331121321122112133221123113112221131112311332111213122112311311222113223113112221121113122113111231133221121321132122311211131122211213211321222113222122211211232221121113122113121113222123211211131211121311121321123113111231131122112213211321322113311213212322211231131122211311123113223112111311222112132113311213211221121332211211131221131211132221232112111312111213111213211231132132211211131221232112111312212221121123222112131112131221121321131211132221121321132132212321121113121112133221121321132132211331121321132213211231132132211211131221232112111312212221121123222112132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113212231121113112221121321132122211322212221121123222112311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122211311123113322113223113112221131112311332211211131221131211132211121312211231131112311211232221121321132132211331221122311311222112111312211311123113322112132113213221133122211332111213112221133211322112211213322112111312211312111322212321121113121112131112132112311321322112111312212321121113122112131112131221121321132132211231131122111213122112311311222113111221131221221321132132211331121321231231121113112221121321133112132112211213322112311311222113111231133211121312211231131122211322311311222112111312211311123113322112132113212231121113112221121321132122211322212221121123222112111312211312111322212321121113121112131112132112311321322112111312212321121113122112131112131221121321132132211231131122211311123113322113221321132132211231232112311321322112311311222113111231133221121113122113121113123112111311222112132113213221132213211321322112311311222123211211131221132211131221121321131112311322311211132132212312211322212221121123222112132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113212231121113112221121321132132211231232112311321322112311311222113111231133221121113122113121113221112131221123113111231121123222112132113213221133122112231131122211211131221131112311332211213211321322113311213212322211231232112311321322112311311222113311213212322211231131122211311123113321112131221123113111231121123222112111312211312111322212321121113122113221113122112132113121113222112311311221112131221123113112211322112211213322112132113213221133112132123123112111312111312212231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113311213212312311211131122211213211331121321122112133221123123211231132132211231131122211331121321232221123113112221131112311322311211131122211213211331121321122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112211322112211213322112111312211312111322212321121113121112131112132112311321322112111312211312111322211322111312211312111322211213211321322123211211131211121332211231131122211311122122111312211213211312111322211231131122211311122113222123122113222122211211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113111231133221121321132122311211131122211213211321322112312321123113213221123113112221131112311332211211131221131211132211121312211231131112311211232221121321132132211331221122311311222112111312211311123113322112132113213221133122211332111213112221133211322112211213322113221321132132211331121321231231121113112221121321133112132112312321123113112221121113122113111231133221121321132122311211131122211213211321322112312321123113213221123113112221131112311332211211131221131211132211121312211231131112311211232221121321132132211331221122311311222112111312211311123113322112132113213221133122211332111213112221133211322112211213322112311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122111213122112311311222112111331121113112221121113122113121113222112132113213221232112111312111213322112311311222113111231133211121312211231131112311211232221132231131122211311123113321112131221123113111231121123222112111312211312111322212321121113122113221113122112132113121113222112311311221112131221123113112211322112211213322112132113213221133112132123123112111312111312212231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113311213212312311211131221132231121113311211131221121321131112311322311211132132212312211322212221121123222112111312211312111322212321121113121112131112132112311321322112111312212321121113122112131112131221121321132132211231131122211331121321232221121113122113121122132112311321322112111312211312111322211213111213122112132113121113222112132113213221133112132123222112311311222113111221221113122112132113121113222112311311222113111231133211121321132221131211321122132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113212231121113112221121321132122211322212221121123222112311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122211311123113322113223113112221131112311332211211131221131211132211121312211231131112311211232221121321132132211331221122311311222112111312211311123113322112132113213221133122211332111213112221133211322112211213322112111312211312111322212321121113121112131112132112311321322112111312212321121113122112131112131221121321132132211231131122211331121321232221121113122113121122132112311321322112111312211312111322211213111213122112132113121113222112132113213221133112132123222112311311222113111231133211121312211231131112311211232221132213211321322113311213212322211231232112311321322112311311222113311213212322211231131122211311123113321112131221123113111231121123222112111312211312111322212321121113122123211231131122211211131221131112311332211213211321322113311213212322211322132113213221133112132123222112311311222113111231131112132112311321322112111312211312111322211322111312211312111322211213211321321112131221123113112221132231131122211211131221133112132113221321123113121113221112131122211332113221122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112311332211211133112111311222112111312211311123113322112111312211312111322212321121113121112133221121321132132211331121321132213211231132132211211131221232112111312212221121123222112311311222113111231133211121321321122111312211312111322211213211321322123211211131211121332211231131122211311123113321112131221123113111231121123222112111331121113112221121113122113111231133221121113122113121113221112131221123113111231121123222112111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321132132211322132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211231131122211311123113321112131221123113111231121113311211131221121321133112132113212221221113122113121113222123211211131211121332211213211321322113311213211322132112311321322112111312212321121113122122211211232221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112211322112211213322112111331121113112221121113122113111231133221121113122113121113221112131221123113111231121123222112111312211312111322212321121113122113221113122112132113121113222112311311221112131221123113112211322112211213322112111312211312111322212321121113121112131112132112311321322112111312212321121113122112131112131221121321132132211231131122211331121321232221121113122113121122132112311321322112111312211312113221133211322112211213322112132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113213221133112132123222113221321132132211331121321232221123113112221131112311322311211131122211213211331121321122112133221121113122113121113222123112221221321132132211231131122211331121321232221121113122113121113222123113221231231121113213221231221132221222112112322211231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122211211133112111311222112111312211312111322211213211321223112111311222112132113213221133122211311221122111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321132132211322132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122211211133112111311222112111312211312111322211213211321322123211211131211121332211231131122211311122122111312211213211312111322211231131122211311122113222123122113222122211211232221121113311211131122211211131221131112311332211211131221131211132211121312211231131112311211232221121113122113121113222123211211131221132211131221121321131211132221123113112211121312211231131122113221122112133221121113122113121113222123211211131211121311121321123113213221121113122113121113222113221113122113121113222112132113213221232112111312111213322112311311222113111221221113122112132113121113222112311311222113111221132221231221132221222112112322211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211132221121311121312211213211312111322211213211321322113311213212322211231131122211311123113223112111311222112132113311213211221121332211211131221131211132221231122212213211321322112311311222113311213212322211211131221131211132221231132212312311211132132212312211322212221121123222112132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113212231121113112221121321132132211231232112311321322112311311222113111231133221121113122113121113221112131221123113111231121123222112132113213221133112132123123112111311222112132113311213211221121332211322132113213221133112132123123112111311222112132113311213211221121332211231131122211311123113321112131221123113112221132231131122211211131221131112311332211213211321223112111311222112132113212221132221222112112322211211131221131211132221232112111312111213111213211231131112311311221122132113213221133112132123222112311311222113111231132231121113112221121321133112132112211213322112111312211312111322212321121113121112131112132112311311222113221321123123211231131122211211131221133112132113221321123113121113221112131122211332113221122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112311332211211133112111311222112111312211311123113322112111312211312111322212321121113121112133221121321132132211331221122311311222112111312211311123113322112132113213221133112132123123112111312211332211311122113122122111312211312111322212321121113121112131112132112311321322112111312212321121113122112131112131221121321132132211231131122211331121321232221121113122113121122132112311321322112111312211312113221133211322112211213322112132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113213221133112132123222113221321132132211331121321232221123113112221131112311322311211131122211213211331121321122112133221121113122113121113222123112221221321132132211231131122211331121321232221121113122113121113222123113221231231121113213221231221132221222112112322211231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122211211133112111311222112111312211312111322211213211321322123211211131211121332211231131122211311122122111312211213211312111322211231131122211311123113322112111331121113112221121113122113111231133221121113122113121113222123211211131211121332211213211321322113311213211322132112311321322112111312212321121113122122211211232221123113112221131112311332111213213211221113122113121113222112132113213221232112111312111213322112311311222113111231133211121321132211121311121321123113121113221112131122211332113221122112133221121113311211131122211211131221131112311332211211131221131211132211121312211231131112311211232221121113122113121113222123211211131221132211131221121321131211132221123113112211121312211231131122113221122112133221121113122113121113222123211211131211121311121321123113213221121113122113121113222113221113122113121113222112132113213221232112111312111213322112311311222113111221221113122112132113121113222112311311222113111221132221231221132221222112112322211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312111322212321121113121112133221132211131221131211132221232112111312111213322112132113213221133112132113221321123113213221121113122123211211131221222112112322211231131122211311123113321112132132112211131221131211132221121321132132212321121113121112133221123113112221131112311332111213211322111213111213211231131211132211121311222113321132211221121332211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211132221121311121312211213211312111322211213211321322113311213212322211231131122211311123113223112111311222112132113311213211221121332211211131221131211132221231122212213211321322112311311222113311213212322211211131221131211132221232112111312111213322112131112131221121321131211132221121321132132212321121113121112133221121321132132211331121321231231121113112221121321133112132112211213322112311311222113111231133211121312211231131122211322311311222112111312211311123113322112132113212231121113112221121321132122211322212221121123222112111312211312111322212321121113121112131112132112311311123113112211221321132132211331121321232221123113112221131112311322311211131122211213211331121321122112133221121113122113121113222123211211131211121311121321123113112221132213211231232112311311222112111312211331121321132213211231131211132211121311222113321132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331121321232221123123211231132132211231131122211331121321232221123113112221131112311332111213122112311311123112112322211211131221131211132221232112111312211322111312211213211312111322211231131122111213122112311311221132211221121332211213211321322113311213212312311211131211131221223113112221131112311332211211131221131211132211121312211231131112311211232221121321132132211331121321231231121113112221121321133112132112211213322112312321123113213221123113112221133112132123222112311311222113111231132231121113112221121321133112132112211213322112311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122111213122112311311221132211221121332211211131221131211132221232112111312111213111213211231132132211211131221131211132221132211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112211322212312211322212221121123222112132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113212231121113112221121321132132211231232112311321322112311311222113111231133221121113122113121122132112311321322112111312211312111322212311322113212221223113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112211322112211213322112111312211312111322212321121113121112131112132112311321322112111312211312111322211322111312211312111322211213211321322123211211131211121332211231131122211311122122111312211213211312111322211231131122211311122113222123122113222122211211232221121113122113121113222123211211131211121311121321123113213221121113122123211211131221121311121312211213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121113222112131112131221121321131211132221121321132132211331121321232221123113112221131112311332111213122112311311123112112322211322132113213221133112132123222112312321123113213221123113112221133112132123222112311311222113111231133211121321132211121311121321123113121113221112131122211332113221122112133221121113122113121113222123211211131211121311121321123113213221121113122123211211131221121311121312211213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121132211332113221122112133221132213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331222113321112131122211332113221122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112311332211211133112111311222112111312211311123113322112111312211312111322212321121113121112133221121321132132211331121321132213211231132132211211131221232112111312212221121123222112311311222113111231133211121312211231131112311211133112111312211213211331121321132122212211131221131211132221232112111312111213322112132113213221133112132113221321123113213221121113122123211211131221222112112322211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131211132221132231131122211211133112111311222112111312211312113221133211322112211213322112132113213221133112132123123112111311222112132113311213211221121332211322311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122111213122112311311221132211221121332211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312111322212311222122132113213221123113112221133112132123222112311311222113111231133211121321132211121311121321122112133221123113112221131112311332211322111312211312111322212321121113121112133221121321132132211331121321231231121113112221121321132122311211131122211211131221131211322113322112111312211322132113213221123113112221131112311311121321122112132231121113122113322113111221131221
11131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211132221121311121312211213211312111322211213211321322113311213212322211231131122211311123113223112111311222112132113311213211221121332211211131221131211132221231122212213211321322112311311222113311213212322211211131221131211132221232112111312111213322112131112131221121321131211132221121321132132212321121113121112133221121321132132211331121321231231121113112221121321133112132112211213322112311311222113111231133211121312211231131122211322311311222112111312211311123113322112132113212231121113112221121321132122211322212221121123222112111312211312111322212321121113121112131112132112311311123113112211221321132132211331121

- subbu September 04, 2013 | Flag

Comment hidden because of low score. Click to expand.

of 0 vote

i am assuming that the number is in the form of digits..if not, then split it into digits and do this:
count=1,j=1;
for(int i=0;i<10;i++){
while(arr[j]){
if(arr[j]==arr[j-1]){
count++;
}
else{
cout<<count;
cout<<arr[j-1];
count=1;
}
j++;
}
cout<<count;
cout<<arr[j];
}

Please let me know if something is wrong.

- alex February 22, 2013 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 votes

what is the arr value ??? is it like [0,1,2,3,4,5,6,7,8,9]

- Anonymous February 22, 2013 | Flag

Comment hidden because of low score. Click to expand.

of 0 votes

Implement LookAndSay function. For example, first, let user input a number, say 1.
Then, the function will generate the next 10 numbers which satisfy this condition:
1, 11,21,1211,111221,312211...
explanation: first number 1, second number is one 1, so 11. Third number is two 1(previous number),
so 21. next number one 2 one 1, so 1211 and so on...
*/

private static LinkedList<String> lookandsay(int i){
//int num = i;
String num = new String();
num = String.valueOf(i);

LinkedList<String> list = new LinkedList<String>();

for (int iter=1; iter<10; iter++){
/*this version can also work, but the number grows rapidly, and will exceed the limit of Integer
if (num == 0) stack.push(num);
else {
while( num != 0){
int tmp = num % 10;
stack.push(tmp);
num = num / 10;
}
}
*/

for(int ind=num.length(); ind>0; ind--){
stack.push(Character.getNumericValue(num.charAt(ind-1)));
}

int current = stack.pop();
int count = 1;
String result = new String();
int next;
while (!stack.empty()){
next = stack.peek();
if (next == current){
count++;
current = next;
stack.pop();
} else {
result = result + count;
result = result + current;
current = stack.pop();
count = 1;
}
}
result = result + count;
result = result + current;
//num = Integer.parseInt(result);
num = result;
System.out.println(num);
list.add(result);

}
System.out.println();
return list;
}

- subbu September 04, 2013 | Flag

Comment hidden because of low score. Click to expand.

of 0 vote

Are these questions for epic builders as well?

- Anonymous February 23, 2013 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

One way to tackle this problem is to treat these numbers as strings, and use two different queues, where the first hold unique occurrences for numbers, while the other queue holds the number of occurrences of each unique occurrence.

public static void LookAndSay(string[] numbers)
{
Queue uniqueNumbers = new Queue();
Queue Occurences = new Queue();
int counter = 1;
string myData;
uniqueNumbers.Enqueue(numbers[0]);
Occurences.Enqueue(1);
numbers[1] = Occurences.Dequeue().ToString() + uniqueNumbers.Dequeue().ToString();

for (int i = 1; i < 10; i++)
{
myData = "";
myData = numbers[i];
uniqueNumbers.Enqueue(myData[0]);
counter = 1;
for (int j = 1; j < numbers[i].Length; j++)
{

if (myData[j] == myData[j - 1])
{
counter++;
}
else
{
Occurences.Enqueue(counter);
counter = 1;
uniqueNumbers.Enqueue(myData[j]);
}

}
Occurences.Enqueue(counter);
while (Occurences.Count != 0)
numbers[i+1] += Occurences.Dequeue().ToString() + uniqueNumbers.Dequeue().ToString(); ;
}
}

- Ahmed Ebaid (University of Connecticut) February 26, 2013 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

public void lookAndSay(String input){
		int i=0;
		/*print the next 10 numbers of the sequence*/
		while(i<10){
			char[] charArray=input.toCharArray();
			StringBuffer sb=new StringBuffer();
			boolean isCont=false;
			int count=0;
			if(charArray.length==1){
				String str="1"+charArray[0];
				System.out.println(str);
				input=str;
				continue;
			}
			else{
				for (int j = 0; j < charArray.length-1; j++) {
					if(isCont){
						count++;
						if(charArray[j]!=charArray[j+1]){
							sb.append(count);
							sb.append(charArray[j]);
							count=0;
							isCont=false;
						}
					}
					else{
						count++;
						if(charArray[j]==charArray[j+1]){
							isCont=true;
						}
						else{
							sb.append(count);
							sb.append(charArray[j]);
							count=0;
						}
					}
				} //end of for loop
				if(isCont){
					count++;
					sb.append(count);
					sb.append(charArray[charArray.length-1]);
				}
				else{
					sb.append(1);
					sb.append(charArray[charArray.length-1]);
				}
			}
			input=new String(sb);
			System.out.println(input);
			i++;
		}//end of while loop
	}

- yoda February 26, 2013 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 votes

@above code
the input is in String format. Converting integer input in to String yields better results.

- yoda February 26, 2013 | Flag

Comment hidden because of low score. Click to expand.

of 0 vote

working java code (at least i think its working)

import java.io.*;


public class LookAndSay 
{
	public static void lookAndSay(String s)
	{
		//Print first 2 iterations
		System.out.println(s);
		
		//Assumes input is a single digit
		s = "1" + s;
		System.out.println(s);
		
		//holds output for single iteration
		StringBuilder output = new StringBuilder();
		
		//loops for next 8 iterations
		for(int x = 2; x < 10; x++)
		{
			//Start count at one (cannot have less than one of the characters)
			int count = 1;
			
			//loop through each character of string
			//ends with the 2nd to last character
			for(int i = 0; i < s.length() - 1; i++)
			{
				//if this character is the same as next character
				if(s.charAt(i) == s.charAt(i+1))
				{
					//increase count by one
					count++;
					//if this is the last iteration
					if(i == s.length()-2)
					{
						//append the count and the character to the output
						output.append("" + count + s.charAt(i));
					}
				}
				else
				{
					//if character is not same as next character
					//append the count and the character
					output.append("" + count + s.charAt(i));
					//reset the count
					count = 1;
					//if this is the last iteration
					if(i == s.length()-2)
					{
						//this means last character is unique, append
						//this information to output
						output.append("1" + s.charAt(i+1));
					}
				}
				
			}
			
			//print output, set string to last output, and reset output
			System.out.println(output.toString());
			s = output.toString();
			output = new StringBuilder();
		}
	}
	public static void main(String[] args) throws IOException 
	{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		System.out.print("Enter a number: ");
		
		String s = in.readLine();
		lookAndSay(s);
	}

}

- Paul March 01, 2013 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

Python code:

userinput = input("Enter the number : ")
output = []
output.append(userinput)
for n in range(10):
output.append("")
count = 0
character = output[n][0]
for c in output[n]:
if c == character:
count += 1
continue
else:
output[n+1] += str(count)
output[n+1] += character
count = 1
character = c
output[n+1] += str(count)
output[n+1] += character
print (output)

- sri harsha March 03, 2013 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

Working C++ code :

It will print only 8 numbers , coz this operation s done based on integer. The 9 th number does not falls under the integer limit

#include "stdafx.h"
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>

void LockAndSaySequence(int num);
int power(int n,int i);
int reversenum(int num);

int _tmain(int argc, _TCHAR* argv[])
{
int num = 0;
LockAndSaySequence(1);
getch();
return 0;

}

void LockAndSaySequence(int num)
{
int prev = num%10, count = 0, rem = 0, newnum = 0 , limit = 0 ;
printf("%d\n",num);
while(num!= 0 && limit < 7 )
{
rem = num % 10;
num = num / 10;
if(prev == rem)
{
count++;
if(num==0)
{
newnum = (newnum *10 + count)*10 + prev;
num = newnum;
printf("%d\n", num);
limit++;
num = reversenum(num);
prev = num%10;
newnum = 0;
count = 0;
}
}
else
{
newnum = (newnum *10 + count)*10 + prev;
prev = rem;
count = 1;
if(num==0)
{
newnum = (newnum *10 + count)*10 + prev;
num = newnum;
newnum = 0;
printf("%d\n", num);
limit++;
num = reversenum(num);
prev = num%10;
count = 0;
}
}
}
}

int reversenum(int num)
{
int rem = 0, newnum = 0;
while(num!= 0)
{
rem = num % 10;
num = num / 10;
newnum = newnum * 10 + rem;
}
return newnum;
}

Can be better solved using strnings operations

- karthiga.m1988 March 04, 2013 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

void lookAndSay(int input){
		System.out.println(input);
		List arr = new ArrayList(1);
		arr.add(input);
		lookAndSay(arr, 1);		
	}
    void lookAndSay(List input, int cnt){
    	int count = 1;
    	if(cnt >= 10) {
    		return;
    	}
    	List newInput = new ArrayList();
		for(int i = 0; i < input.size(); i++) {
			if(i == input.size()-1) {
				newInput.add(count);
				newInput.add(input.get(i));
				break;
			}
			if(input.get(i) == input.get(i+1)){
				count++;
			}else {
				newInput.add(count);
				newInput.add(input.get(i));
				count =1;
			}
		}
		for(int i = 0; i < newInput.size(); i++)
			System.out.print(newInput.get(i));
		cnt++;
		System.out.println();
		lookAndSay(newInput, cnt);
	}

- abhradeep.kundu March 06, 2013 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

import java.util.Scanner;


public class LookAndSay {

	public static void lookAndSay(String s)
	{

		System.out.println(s);
		s = "1" + s;
		System.out.println(s);

		StringBuilder output = new StringBuilder();
		for(int x = 2; x < 10; x++)
		{
			int count = 1;
			for(int i = 0; i < s.length() - 1; i++)
			{
				if(s.charAt(i) == s.charAt(i+1))
				{
					count++;
					//if this is the last iteration
					if(i == s.length()-2)
					{
						//append the count and the character to the output
						output.append("" + count + s.charAt(i));
					}
				}
				else
				{
					//if character is not same as next character append the count and the character
					output.append("" + count + s.charAt(i));
					//reset the count
					count = 1;
					//if this is the last iteration
					if(i == s.length()-2)
					{//this means last character is unique, append this information to output
						output.append("1" + s.charAt(i+1));
					}
				}				
			}
			
			//print output, set string to last output, and reset output
			System.out.println(output.toString());
			s = output.toString();
			output = new StringBuilder();
		}
	}
	public static void main(String[] args) //throws IOException 
	{
//		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
//		System.out.print("Enter a number: ");
//		
//		String s = in.readLine();
	Scanner sc = new Scanner(System.in);
	System.out.print("Enter a number: ");
    String s = sc.nextLine();
    sc.close();
  
	
		lookAndSay(s);
	}

}

- disun March 08, 2013 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

public class LookAndSay {
	static int countOfSeriesToPrint = 0;
	static final int TOTAL_NUMBER_OF_TIMES = 8;
	
	/*************************************************************************************
	 * @param args
	 */
	public static void main(String[] args) {
		lookAndSayFunc(1);
	}
	
	/*************************************************************************************
	 * 
	 * @param number
	 */
	public static void lookAndSayFunc(int number){
		System.out.println (number);
		
		String str = String.valueOf(number);;
		int i =0, currentNumberCount = 0;;
		char currentNumber ='a';
		char nextNumber;
		int changedIndex = 0;
		String finalNumber = "";
		while( i < str.length()){
			if(i == changedIndex){
				currentNumber = str.charAt(i);
			}else{
				nextNumber = str.charAt(i);
				if(nextNumber == currentNumber){
				}else{
					finalNumber = finalNumber+""+currentNumberCount+""+currentNumber; 
					currentNumberCount = 0;
					changedIndex = i;
					continue;
				}
			}	
			currentNumberCount ++;
			i++;		
		}
		finalNumber = finalNumber+""+currentNumberCount+""+currentNumber;
		if(++countOfSeriesToPrint == TOTAL_NUMBER_OF_TIMES){
			return;
		}
		lookAndSayFunc(Integer.parseInt(finalNumber));
	}
}

- Anand J March 11, 2013 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

public class LookAndSay {
public void solution(int input) {
String in = Integer.toString(input);
int i = 0;
int count;
while (i < 10) {
char[] charArray = in.toCharArray();
StringBuffer sb = new StringBuffer();
if (charArray.length == 1) {
count = 1;
sb.append(count);
sb.append(charArray[0]);
} else {
for (int j = 0; j < charArray.length; j++) {
count = 0;
int temp = j ;
while (charArray[j] == charArray[temp]) {
count++;
temp++;
if (temp >= charArray.length)
break;
}
j = temp - 1;
sb.append(count);
sb.append(charArray[j]);
}
}
System.out.println(sb.toString());
in = sb.toString();
i++;
}
}

public static void main(String[] args) {
LookAndSay l = new LookAndSay();
l.solution(1);
}
}

- Anonymous March 17, 2013 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

Python version using list with string.
Working code:

"""


* Using string manipulation and concat the results.

Implement LookAndSay function. For example, first, let user input a number, say 1. Then, the function will generate the next 10 numbers which satisfy this condition: 
1, 11,21,1211,111221,312211... 
explanation: first number 1, second number is one 1, so 11. Third number is two 1(previous number), so 21. next number one 2 one 1, so 1211 and so on...
"""


def lookAndSay(number):
  if number is None or type(number) != type(1):
    print 'Invalid Number!'
    raise SystemExit
    
  result = []
  result.append(str(number))
  
  for i in range(10):
    tmpOutput = []
    # print result
    cur = result[i][0]
    count = 1
    for j in range(1, len(result[i])):
      if result[i][j] != cur:
        tmpOutput.append(str(count))
        tmpOutput.append(cur)
        cur = result[i][j]
        count = 1
      else: # when result[i][j] == cur
        count += 1
      # print tmpOutput  
    tmpOutput.append(str(count))
    tmpOutput.append(cur)
    if len(tmpOutput) == 0:
      result.append('1' + cur)
    else:
      result.append(''.join(tmpOutput))
      
  print ', '.join(result)
  
if __name__ == '__main__':  
  lookAndSay(1)

- tosay.net March 19, 2013 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

Here's a working version in R. Very simple algorithmic approach.

num <- 1
print(num)
for (i in 1:10) {
current.digit <- 1
storage <- c()
counter <- 0
repeat {
current.digit <- current.digit + counter
if (current.digit > nchar(num)) {
break
}
if (current.digit == nchar(num)) {
k <- substr(num,current.digit,current.digit)
counter <- 1
storage <- paste(storage,counter,sep='')
storage <- paste(storage,k,sep='')
break
}
counter <- 0
k <- substr(num,current.digit,current.digit)
repeat{

if (substr(num,current.digit+counter,current.digit+counter)!=k) {
break
}
counter = counter + 1
}

storage <- paste(storage,counter,sep='')
storage <- paste(storage,k,sep='')
}

num <- storage
print(num)
}

- Codin' Dude April 14, 2013 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

• using System;
• using System.Collections;
•
• class Function
• {
• public ArrayList function(string str1,string str2)
• {
• ArrayList arr = new ArrayList();
• arr.Add(str1);
• int count = Int32.Parse(str2);
• if(count < 0)
• Console.WriteLine("Error Number!");
• else if(count ==1)
• Console.WriteLine(str1);
• else if(count > 1)
• {
• for(int i = 1; i < count; i++ )
• {
• char[] temp = new Char[arr[i-1].ToString().Length];
• temp = arr[i-1].ToString().ToCharArray();
• int c = 1;
• string s = "";
•
• for(int j = 0; j < temp.Length; j++)
• {
• if(j+1<temp.Length-1 && temp[j] == temp[j+1])
• c++;
• else if(j+1 < temp.Length-1 && temp[j] != temp[j+1])
• {
• s += c.ToString() + temp[j];
• c = 1;
• }
• else if(j+1 == temp.Length-1 && temp[j] == temp[j+1])
• {
• c++;
• s += c.ToString() + temp[j];
• break;
• }
• else if(j+1 == temp.Length-1 && temp[j] != temp[j+1])
• {
• s += c.ToString() + temp[j] + "1" + temp[j+1];
• break;
• }
• else if(j == temp.Length-1)
• {
• s += c.ToString() + temp[j];
• }
• }
• arr.Add(s);
• s = "";
• }
• }
• return arr;
• }
•
• static void Main()
• {
• Console.WriteLine("Please input the first number:");
• string str1 = Console.ReadLine();
• Console.WriteLine("How many terms do you wanna output?");
• string str2 = Console.ReadLine();
• Function f = new Function();
•
• ArrayList arr = new ArrayList();
•
• arr = f.function(str1,str2);
• Console.WriteLine("The count array is :");
• for(int i = 0; i < arr.Count; i++)
• Console.WriteLine(" {0} : {1} ",i+1, arr[i]);
• }
• }

- C# implementation, at lease it works! April 18, 2013 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

public static String lookUp(String num)
{
StringBuilder str=new StringBuilder();
StringBuilder str1=new StringBuilder(num);
char init=str1.charAt(0);
//str1.append(' ');
int times=1;
if(str1.length()==1)
{
str.append(times+""+init);
return str.toString();
}
for(int j=1;j<(str1.length());j++)
{

if(init!=str1.charAt(j))
{

str.append(times+""+init);
times=1;
init=str1.charAt(j);

}

else
times++;
if(j==str1.length()-1)
{
str.append(times+""+init);
return str.toString();
}

}

return str.toString();
}
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub

String num="1";
for(int i=0;i<10;i++)
{
System.out.println(num);
num=LookUp.lookUp(num);
}
}

}

- krismo June 01, 2013 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

#include <stdio.h>
#include <string.h>
void fun(char *s,char *s1);
int main(int argc, char const *argv[])
{
	int i=0;
	char str[10]="1",str1[10];
	for (i = 0; i < 10; ++i)
	{
		fun(str,str1);
		strcpy(str,str1);
	}
	return 0;
}
void fun(char *s,char *s1)
{
	int count=0,i=0,j=0;
	for (i= 0; i <strlen(s); ++i)
	{
        if(i==0)
        {	
         	count=1;
        }
        else if(s[i]==s[i-1])
 	    {
 	    	count++;
    	}
    	else
    	{
    		s1[j++]=count+'0';
    		s1[j++]=s[i-1];
    		count=1;
    	}
	}
	s1[j++]=count+'0';
	s1[j++]=s[i-1];
	s1[j]='\0';
	printf("%s\n",s1);
}

- mani 4m sklm June 26, 2013 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

package epic;

public class LookAndSay {
private static int count;

public static String LookAndSay(String i) {

String result = "";
int len = i.length();
if (count-- == 0)
return "";
int l = len;
String c = "";
int s = 0;
String t = i.substring(0, 1);

for (int p = 0; p < l; p++) {
c = i.substring(p, p + 1);
if (c.equals(t)) {
s++;
} else {
result = result + String.valueOf(s) + t;
s = 1;
t = c;
}
if ((p + 1) == l) {
result = result + String.valueOf(s) + t;
}
}
return result + "\n" + LookAndSay(result);
}

public static void main(String[] args) {
count = 10;
System.out.println(LookAndSay.LookAndSay("1"));
}
}

- sm July 19, 2013 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

public class LookAndSay{
           	
	public static void main(String[] args) throws Exception
	{ 
	     String s = "1";
	     String ss = "";
	     for(int j = 0;j<10;j++)
	     {
	         s=s+"0";
	     for(int i=0;i<s.length()-1;i++)
	     {
	    	 count =1;
	    	 while(s.charAt(i)==s.charAt(i+1))
	    	 {
	    		 count++;
	    		 i++;
	    	}
	    	 ss = ss+count+s.charAt(i);
	     }
	     System.out.print(ss + " ");
         s = ss;
         ss="";
	     }
	}
}

- Kanha August 15, 2013 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

this is a working code i wrote in "C". Though I have taken an upper bound of 100 digits, you can change it to whatever value you want. Indeed you can make it dynamic too.

#include <cstdio>
#include <iostream>

using namespace std;

int main()
{
    int n, *arr, i, j, ct=0, temp, flag=0, *brr;
    cin>>n;
    arr=new int [100];
    brr=new int [100];
    for (i=0; i<100; i++)
    {
        arr[i]=-1;
    }
    for (i=0; i<100; i++)
    {
        brr[i]=-1;
    }
    arr[0]=1;
    cout<<"1"<<endl;
    while (n--)
    {
        j=0;
        temp=arr[0];
        ct=0;
        for (i=0;i<100; i++)
        {
            if (arr[i]==temp)
            {
                ct++;
            }
            else if(arr[i]!=temp && arr[i]!=-1)
            {
                brr[j]=ct;
                j++;
                brr[j]=temp;
                j++;
                temp=arr[i];
                ct=1;
            }
            else if (arr[i]==-1)
            {
                brr[j]=ct;
                j++;
                brr[j]=temp;
                flag=1;
            }
            if (flag==1)
            {
                for (i=j+1; i<100; i++)
                {
                    brr[i]=-1;
                }
                break;
            }
        }
        for (i=0; i<100; i++)
        {
            if (brr[i]!=-1)
            {
                cout<<brr[i];
            }
            arr[i]=brr[i];
        }
        cout<<endl;
        flag=0;
    }
    return 0;
}

- Meraj Ahmed November 09, 2013 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 votes

Sorry, its in C++

- Meraj Ahmed November 09, 2013 | Flag

Comment hidden because of low score. Click to expand.

of 0 vote

public ArrayList<String> countAndSay(int n) {
		ArrayList<String> result = new ArrayList<String>();
		result.add(String.valueOf(n));
		for(int i=1; i<10; i++) {
			String tempString = result.get(i-1);
			String tempResult = "";
			int j = 0;
			while(j<tempString.length()) {
				int k = j;
				int count = 1;
				while(k<tempString.length()-1&&tempString.charAt(k)==tempString.charAt(k+1)) {
					count++;
					k++;
				}
				tempResult += count +""+ tempString.charAt(j);
				j = k+1;
			}
			result.add(tempResult);
		}
		return result;
	}

- sz2376@columbia.edu December 01, 2013 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

import java.lang.Math;

public class LookAndSay {

	public static void main(String[] args) {

		lookAndSay(Integer.parseInt(args[0]), Integer.parseInt(args[1]));

	}

	public static void lookAndSay(int d, int n) {

		int term = d;

		for( int i = 0; i < n; i++) {

			int exp = 0;
			int nextTerm = 0;
			System.out.println(term);

			while(term != 0) {
				int dig = term % 10;
				int ctr = 0;
				while( term % 10 == dig) {
					term /= 10;
					ctr++;
				}
				nextTerm += dig * (int)(Math.pow(10, (double)(exp++)));
				nextTerm += ctr * (int)(Math.pow(10, (double)(exp++)));
			}
			term = nextTerm;		
		}
	}
}

- tp December 23, 2013 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

public void generateLookAndSay(int n,String a)
	{
		
		
		for(int i=0;i<n;i++)
		{
			System.out.println(a);
			
			char[] ch= a.toCharArray();
			int count = 1;
			a = "";
			for(int j=0;j<ch.length-1;j++)
			{
				if(ch[j]==ch[j+1])
					count++;
				else
				{
					a = a + count + ch[j];
					count = 1;
				}
				
			}
			a= a+ count+ch[ch.length-1];
			
		}
		
	}
public static void main(String[] argv)
	{
		LookAndSay ls = new LookAndSay();
		ls.generateLookAndSay(8,"1");
	}

- Harish A March 25, 2014 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

public class LookAndSay
{
	public static String[] lookAndSay(String initialNum)
	{
		String[] result = new String[10]; // result array
		String currentSeq = initialNum; // initialize current seq

		// outer loop to generate 10 sequences
		for (int i = 0; i < 10; i++)
		{
			char currentDigit = currentSeq.charAt(0); // current digit
			int cnt = 1; // number of repetitions of that digit

			String newSeq = "";
			for (int j = 1; j < currentSeq.length(); j++)
			{
				// count current digit
				if (currentSeq.charAt(j) == currentDigit)
					cnt++;
				else
				{
					// append count of current digit along with the
					// digit itself
					newSeq += cnt + "" + currentDigit;
					// reintialize current digit and count
					currentDigit = currentSeq.charAt(j);
					cnt = 1;
				}
			}
			newSeq += cnt + "" + currentDigit;
			result[i] = newSeq;
			currentSeq = newSeq;
		}
		return result;
	}

	public static void main(String[] args)
	{
		String[] las = lookAndSay("1");
		for (String seq : las)
			System.out.println(seq);
	}
}

- Mahmoud El-Maghraby June 29, 2014 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

String lookAndSay(int num){
		return String.valueOf(num) +" : "+ lookAndSay(String.valueOf(num),1);
	}
 String lookAndSay(String input, int itrCount){
		if(itrCount > 10){
			return "";
		}
		if(input != null){
			char[] inputArray = input.toCharArray();
			char currentNum = inputArray[0];
			int count = 1;
			StringBuilder output = new StringBuilder();
			
			for(int i=1;i<inputArray.length;i++){
				if(inputArray[i]==currentNum){
					count++;
				}
				else{
					output.append(count);
					output.append(currentNum);
					currentNum = inputArray[i];
					count = 1;
				}
			}
			output.append(count);
			output.append(currentNum);
			output.append(" : "+lookAndSay(output.toString(),++itrCount));
			return output.toString();
		}
		else{
			return null;
		}

}

- Vinoth September 27, 2014 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

public class Solution {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String s = looksay("1");
		s = looksay(s);
		s = looksay(s);
		s = looksay(s);
		s = looksay(s);
	}
	
	public static String looksay(String str) {
		char ch[] = str.toCharArray();
		String new_str = "";
		int i=0;
		int count=1;
		int len = str.length();
		
		System.out.println(str);
		while(i<str.length()) {
			if(i<str.length()-1) {
				if(ch[i]==ch[i+1]) {
					count++;
				}				
				else {
					new_str = new_str + count + "" + ch[i] + "";
					count=1;
				}				
			}						
			else {
				new_str = new_str + count + "" + ch[i] + "";
				count=1;				
			}
			i++;
		}
		System.out.println(new_str);
		return new_str;
	}
}

- Ansh Bahri October 29, 2014 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

import java.util.Random;


public class LookAndSay {

	public static void main(String[] args) {
		int n;
		if(args.length == 1)
			n = Integer.parseInt(args[0]);
		else
			n= (new Random()).nextInt(10) + 1;
		looknsay(n);		
	}

	private static void looknsay(int n) {
		System.out.println(n);
		String s = "1";
		for(int i=1;i<n;i++){
			s = genNext(s);
		}
		System.out.println(s);
	}

	private static String genNext(String s) {
		StringBuffer sb = new StringBuffer();
		int count;
		for(int i=0;i<s.length();i++){
			count = 1;
			while( i+1 < s.length() && s.charAt(i) == s.charAt(i+1)){
				++i;
				++count;
			}
			sb.append(count);
			sb.append(s.charAt(i));
		}
		return sb.toString();
	}

}

- Kani90 November 23, 2014 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

class Epic
{

private static void LookAndSay(String in, int limit) {
if(limit == 0) return;
String result = "";
int count = 1;
int i = 0;
for(i = 0; i < in.length()-1; i++) {
if(in.charAt(i) == in.charAt(i+1)) {
count++;
} else {
result += Integer.toString(count)+in.charAt(i);
//System.out.print(result);
count = 1;
}
}
if(count >= 1){
result += Integer.toString(count)+in.charAt(i);
}
System.out.println(result);
LookAndSay(result,--limit);
}
public static void main (String[] args) throws java.lang.Exception
{
String input = "1";
LookAndSay(input,3);
}
}

- HuiZhou November 24, 2014 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

class Epic
{
	
	private static void LookAndSay(String in, int limit) {
		if(limit == 0) return;
		String result = "";
		int count = 1;
		int i = 0;
		for(i = 0; i < in.length()-1; i++) {
			if(in.charAt(i) == in.charAt(i+1)) {
				count++;
			} else {
				result += Integer.toString(count)+in.charAt(i);
				count = 1;
			}
		}
		if(count >= 1){
			result += Integer.toString(count)+in.charAt(i);
		}
		System.out.println(result);
		LookAndSay(result,--limit);
	}

       // Test
	public static void main (String[] args) throws java.lang.Exception
	{
		String input = "1";
		LookAndSay(input,3);
	}
}

- HuiZhou November 24, 2014 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

import java.util.Random;


public class LookAndSay {

	public static void main(String[] args) {
		int n;
		if(args.length == 1)
			n = Integer.parseInt(args[0]);
		else
			n= (new Random()).nextInt(10) + 1;
		looknsay(n);		
	}

	private static void looknsay(int n) {
		//System.out.println(n);
		String s = "1";
		System.out.println(s);
		for(int i=1;i<n;i++){
			s = genNext(s);
			System.out.println(s);
		}
		System.out.println(s);
	}

	private static String genNext(String s) {
		StringBuffer sb = new StringBuffer();
		int count;
		for(int i=0;i<s.length();i++){
			count = 1;
			while( i+1 < s.length() && s.charAt(i) == s.charAt(i+1)){
				++i;
				++count;
			}
			sb.append(count);
			sb.append(s.charAt(i));
		}
		return sb.toString();
	}

}

- crazykani November 29, 2014 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

using System;

namespace Number
{
    class Program
    {

        static void Main(string[] args)
        {
            PrintNumbers(10, 1);
        }
        private static void PrintNumbers(int length, int seed)
        {
            string number = seed.ToString();
            while (length > 0)
            {

                char curr;
                int count = 0;
                curr = number[0];
                string result = "";
                for (int i = 0; i < number.Length; i++)
                {
                    if (curr == number[i])
                        count++;
                    else
                    {
                        result += count.ToString();
                        result += curr;
                        count = 1;
                        curr = number[i];
                    }
                    if (i == number.Length - 1)
                    {
                        result += count.ToString();
                        result += curr;

                    }
                }
                Console.WriteLine(result);
                length--;
                number = result;
            }
        }
    }
}

- JR December 18, 2014 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

I think the initial input should be limited to 0~9. They generate the next number in a way that first count the appearance of continuous same digit and put the count before that digit. Quite similar to compressing string.

public static void LookAndSay(int input){
		String str= String.valueOf(input);
		System.out.println(str);
		if(str.length() == 10){
			return;
		}
		else{
			String result = "";
			int cnt = 1;
			char cur = str.charAt(0);
			for(int i=1; i<str.length(); i++){
				if(str.charAt(i) == cur)
					cnt++;
				else{
					result = result + String.valueOf(cnt) + cur;
					cur = str.charAt(i);
					cnt = 1;
				}				
			}
			result = result + String.valueOf(cnt) + cur; 
			LookAndSay(Integer.parseInt(result));
		}
	}

- NathanLRF January 04, 2015 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

public class Number {

	public static void main(String[] args){
		String input = args[0];

		generateOutput(input);
	}


	public static void generateOutput(String in){	
		System.out.println(in.toString());
		for(int i = 0; i < 10; i ++){	// 10 times through algo
			int curPos = 0;
			List<NumNode> ls  = new ArrayList<NumNode>();
			ls.add(new NumNode(in.charAt(0), 0));
			for( char curr : in.toCharArray()){
				if (curr == ls.get(curPos).getNumber()) ls.get(curPos).incCount();
				else { ls.add(new NumNode(curr, 1));
				curPos ++;
				}
			}	

			Iterator<NumNode> itr = ls.iterator();
			StringBuilder sb = new StringBuilder();
			while(itr.hasNext()){
				NumNode nn = itr.next();
				sb.append(nn.getCount() +"" + nn.getNumber());
			}
			System.out.println(sb.toString());
			in = sb.toString();

		}
	}
}

public class NumNode {

	private char number;
	private int count;

	public NumNode(char number, int count){
		this.number = number;
		this.count = count;
	}

	public char getNumber(){
		return number;
	}
	public void incCount(){
		count ++;
	}
	public int getCount(){
		return count;
	}


}

- John Doe February 15, 2016 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

/* 
look and say sequence 
en.wikipedia.org/wiki/Look-and-say_sequence
*/

def look_and_say_next( cur_no ){
  digits = str( cur_no ).toCharArray 
  count = 1 
  buf = ""
  past_digit = digits[0]
  for ( inx : [1:size(digits)] ){
    cur_digit = digits[ inx ]
    if ( cur_digit != past_digit ){
       buf += ( str( count ) + str( past_digit) )
       past_digit = cur_digit 
       count = 1  
    } else {
      count += 1 
    }
  }
  buf += ( str( count ) + str( past_digit) )
  int( buf )
}
las = list( 1 )
for ( inx : [0:10 ] ){
  next = look_and_say_next( las[-1] )
  las += next
  println( next )
}

- NoOne April 18, 2019 | Flag Reply

Comment hidden because of low score. Click to expand.

CareerCup

Epic Systems Interview Question for Software Engineer / Developers

Books

Videos

Resume Review

Mock Interviews