Ticket 7118
Problem 1680 -c
Submission 157127941
View hacks & all small testcases

Unable to dry run this testcase?
Try making a new request with small values of n_high, t_high, *_high, etc.


Retry
Input
797
1111
101010110100101001
00
110011000101001
00
010001
00000000000000000100000000
10000000000000
10000000000
1111
0000000
1111000
1111111001110011110001001
111
110011111111
00000
0001000000100
100011011100001010000100100000
0010111001010110001
000001000000
00010000010110100000010000101
00000
010000000000100011000101010
000011010010111001001001010
0011101001000
101000100000001000
011011111111
01101000110111101001
11111011110010110
1001111011111111
00010001110010000010001000
001
1101111111111
0001010000001000000000000000
1010110001010010101100110
11000000
0000000000000010
110
10000000
01001111001111000101011
0000000100001000
00100110010101111010011
1111111111101111011110
011
1110100110111110011110
010
01010011111001010100
000000
00000000000000100000000
11
10100
100
10
101001101010101101111100000000
11011111001110110110001110010
10111110110101111101110011101
101111111101
01
10101110000000000000111100001
01011101100111000010000000
011110
10010101111001111111011010
11001111111111110111
11011100110
010010000000010
101111111101101111101101001
00100100
0000000000000010
0000110110010110
1111111111
011010001011000100
11001010001101110011000101101
0000
110100000001101110001101111001
1
11
00001010
101100110000
11011111111110111111111111
01011100011010100010
0
0111101
0110
100001100111100010
1011110101
11111011111
1
11111
001000
0000000000010000
101011110010011
111111111111111111111
1
011010
00011
110111111
00
000100001000011
000110111000011001011101
1110010100110100100101111
00000001000010001
110011010111101110111011
0000000000100000
111100110
011101111110101101111111111
000000000000000000000000000
1111111111110010111
11111001110111000010011100
010000000010
11010011000110111110011110000
1101110101
111011
1111111111111111111
000000100100000
010000000010000000000010
11111011
00
111111111111111111
100
00000000000000000010000
1011011101111010101100
1111111111
010001000000000010101001
01001101001000
111110110110011111111111111111
000111100000
1111111111011110
0000010100011
0000000000000000000000000
00000
1011111
0110110110
1111111110
00000000000000000000000000000
11111111111111111111111
0000000000000000010000000000
010100011011110111
11111011111111111111111111
00000100000100
101100000101
0000000000
0010000
00000
11100000111010011100
1
00
100000100100100000000
1001100110000010100
010001001
000
11110011110000011101
001110001
000000010001
10101111111111110111101111
000000001000000110
1111101111111111111111111
111101101011101
111111101001111101111
000000000000
00000010001000000
000101001000110000000000001
11011111111111111111
001000010001000000
01101110011111111
0000000000000
000
111101110110011100001
001001
00100001110
111
00000000000000000100100
111101101
00000000000110000000
00000110110011010
01100111111101
11111111011111111111
00000000000000000000000000
011111000000101101000010100101
11001000011
0001000101001010000
111111111111
1001110011011110101111011111
10111101110100
0
00
00010001100010000
11111111111111
00
1111111111111111111111111
01000110100000000000000000
00001001100101
0101011001010111011011111
0010000001
1011101001010101001110
1000
0111101110110110
010100000000101000000011000000
000001000000101101
00100000000
0111011110101110
11111
1111
1111001111111
0
11111111111111110111111
0000000
101111
11110000000101101
00100010010001000100000000001
11111111111010111011111111111
00101111011010100111000111
00011110101101000
1110111101111111111101111
00
11111101110111111111111111011
111111101111111110101011111
111
11111111111
111111011100011010111010
1100
1110
01011000010010000010
1100111011100111001111101011
0010000001100001000100000
00000000010
01101100
000000
010101100100110110100
00110010
011
1011111001111011
1100010111100111000001011001
0000000000000000000000000
11111111
00000001
00000000001000
0111101111111111111
110000110000101001000000
001110001000000000
11011000111011001101110
1001010111011
1111011111111000111011111
0100001000000010111
0000100100000010000000000000
110111011011111110
100101111110
1111100010110111
001000111100010000100111010
111000111001001011011001000110
0000000000000010
10001101111011111
00000000000000000001
111110101111111111100111010011
11
100000000000000000000010000
000001001110110100001000011110
11111101111111111111
0100001101011100100110111
0111100111101
0000000000000000000000000000
10010001010000001100
101111100
01011111011011
11111111111111111111111111111
1000000000000
000000000000000000010010
100
100
1010011000000
01011011000011110101100
111011
10101
1101110
001001101
0000
11
10001111
11111111111011111110010101
01100100001001001110000000100
111
01001111011001101011000001111
101111010000111001000
1111111111
1111010011111111011
00001000000010000001000000110
010101111111010101101010
0001000100000110000100000000
110100010
111101111011110111111011111111
111
1100
111
11000
1111
000110
0000111100
10
011011011111010101011101000111
1001111
000000
1001111010111011
111111111
0110000110111000
11101
1
0
111111111111
00000000000000101000000000
1011
000000101000000100010010
10101
100000000000000000000000000000
010100000010001001001100001
111101111011110
111110
01110010000000000100000010
0000
1111111111111111111111111
100110010011110011010011111
110110
000000000
00000
111111110111011
11
00011101011011101011110001
00000000000000000000
1101011101
1111011111010110111011111110
00000100000000000000000100001
00100000011100100
001000000000000000000100
0010001010001
100100001
11011101010011011000011111
01111
1110111111101111
11111111111110111111
10
001100000111101
1101110111110000111111
111001010111110110100
0
0000000
00
1101111101111111111
111111111111111111111111
0000000000
0011010111
0
00000000000
1001111111111
000100010110100000000001101
1011011111111101110111
000111000010010000001000110000
1110100101111100001011000
000011000
1110110011111111111111110
0100001
011011
000111111100110110111111111
00100
01001
0001110001010110000001110
111101111111111011100111111
1111111111111
00101000
000000100100001000
000
01111110100100111
00010010010110111101100001
011000100000111000
100100101111010011110001000
00001
10100000101
01101101011
100000000000000000
011111000111100001
111101011
101
1010001110001000001100
000101010
11111111011010011111111101111
0000000000000000000000
0000000100000
00000100100000101
010000001000001011111101000100
1101101111111
0000011010111111011011100001
111110111111111111
10000000
000101110110010111110
1111111111111
11111101100101011100011110111
0000
00000000000100000010000000000
111011111111110
1111111111111111111111
0000000000000
00011
00110
0101101
001011
00010
00010
1100111011110110111110
01010000100110001101100
111110111111111111111111111111
000001011
111111111
101100
000010000000000010000000000000
01111100101101101011011010
01111011101101
111011111
1101
00010001
000000000000000
0000000000000000000000000
11010111110100
11101110110011111101111
100001110010111001000100100
00011010101001101100110110101
111111111100111111
11
0110
00010
00010001010011
111111111111101111011
001100010111010001110000101110
111001
00000000000100000
00111100100101011111111111
01001001000000110100010100010
110001
000000011001010000110
0000000000000000
0010000001000000
1111111111111111111111
0000000000000000000000
0101110111
110000100000101100
000001000000100000010000100
1110010011
000000
11
1
11011111010111
11111111111
1111
00000000
11010100101001
100100011110011
1011111111111111111111111011
11111110011110111110111100
10011
0001111111001
11111111111111110011111
00001000000000000000000000
1000001010000000001001000000
111
0000000010000000
11111111110111011111101
111111111111111111111
0000001001111
101
101101
011011110
001001010
1000000001000
0000001010000100
1110000000100111000011000000
000000000000
11111111111111
01101110
00101101000110011
11111111111111110111
1
0111110001100101110011001011
101100000
1101110111101010010111110
110111000110110111101110
101111110111100100111110101010
1
1111111111111111111111111
0000000
01000000010000000
000110010111010010
111111111111111
00000001
0010000000000
101010101100000011
0011010001000100001
0101000100
111111111111111111
0111100110001111101001010101
1111111111111111111111111
01001000010000011000
001100
01100100001001000
1000
01000110101010000000000
111111111011
1111
001000000000010110000010
0010001000
00000000000
1111111110111011
0111111111111010111111111011
0110011000100100010000000000
000110100
1000001000000
10000000000000001000001
111101000110100111010111011101
111111111111110111
01101011011110101
00000000
111101
01000
1
00010000000000000100
0000
0000001
1111111
10100001100110010010010000
0000
0
0011011000110010000000011
10000000
0100011101110101100
000001000001110100101001
0000010100100000001100
0000
00101100000
000000011001000
100
11111111111111111110011111
1100100010001
010010011110100000000
11110011110011010000101010
111111111101111111111111
000101001000
10001
0100110101110011000111010110
110110110111011110010101
0000000000000000
101111011111111100111111111011
01011001010001110
101
101001010
000000000000000000000000
1101111010000010100011
1111000101011001001100101011
010000001000
11111111111111010111
001000100000000000000000000100
0000000000
1101010001010101100000111111
111111011110110010011001
111111111
101011011101011110001
1100000000000001000011000
00000
000000010000000100000000000
000001000010110011010000011
000
000101000000101010
011001010111000100000100100000
11101
01000000010000000001100000
001000
0010110010110
1
0010110111001
0000101010010001
000011111111111111110111
010000110000000100010010110000
1101101111
1001100011001
1111
0
1111101111111111
111001010000000
100100111110100111110001001
010010110111011
100000000
000000100
000111100101100000000
010001111001101111
0011101100101001
10110
00001010110100
010100000011010111000101101
0100011
0
1101001000
1111111111101
1111100111111
00100100111000011110101
01
11111111111
1111111001010111111010111101
1111111101111111110
0011111001010000010101
1111101111110111011
11111111111011
1111111111111111101111111
001100000
1011
01000000110001001101
010000100
1101100011010110010000
1110101111110
000110000001000000000
0100000000000000000000000
100001110110100110011101011
1000010110001011011010110100
10111111111110111011101111
10000000011111000000
1100100010
101111111000010
1111101100100
01100
0000000100000000000
0000101001000011110
111
101101010
11111111110111111001101
010010
00010000
1111111110
11101100101011010
000000001000000100011000000000
101111111111111101111111111111
0101100000
1000000
000000000
1000000000100011000000000010
111001110
1110010111
0000
00101000010
011101100111111111110111111
0011000000001010011010
0000000111110000000
1111111
000000100000000000000000
1111111110111101111111
01111001
11111
100000011001001000110
0111101111111011101001011
1111000111011000010010
0001011011100
10101111111111111
1011
0110111100001110101101110
10000110
11111001111110110000
1000001000000000
1100000110100
00011
1101110110111
11111
0000000001000
100110100011011110011001111
0000
00110111111011
0000000010000
11111111111110
0001000001
0000
010011100111011000010110
1111111110
101000
11111111111111111111
1001011101000010000110001111
100001101100000011110000110000
1011110100
0011101001001001110
111111011111111111111
0000110110
00111110101001011
0000100
0
111111111
111110101111
00100100010001011000
11111011111
11011010101010
010110001000110111
11101111111110111110010011111
000000000000010100000
1000000000000010000000000000
10011001000001010101010010100
0000
0001
11110111101011
111110011100000101111
11111111111111011111011000
111110011111111110110111
00
00
01000000000
1110000110011111111011111001
111111
1101011011
11111011111110111111110
000000000
11
101
111111111111111111111111
011111001
100011000001010001
1111111111101
1111111111110111111
101101110011
110101111111111111111
001000010110110100
000
11001011011110
11010001011000000010101010
11000111000
111111011111
010011111
011110111111010111111100
000000001001000000
000010101000000100
0110111111
111
000000
11111
11010001000
0011101110110111100110001
110111
000110111101
01111111111111
000000000010
0000001000100
0010011111000
110110011111001
11111111101111111111
000000000001000000000100
001
11111111111111111111111
010
01101111100001000101110111111
11111
01010000100101110010111101110
1001000000
01100111111010011111
10011111010
111000111000
010100011001110000
1111111111111111111111101111
100100011000110001
01111110110010110001111010110
110011100101111001
0000010000100000010
11111101111
1111110111110111111111111
000011000000010
000010110
0101111111011101111
011
1111111111
101001111
1111010101010110101
0000001001
0000000010110
00000000000000001000
011111111
11111011011
11011001011101111100101001
000101000001011000
11111010101
0011000011001000
10101110
0111000101000001100000000
101
001000010000001000000100
0001010011110111010010010
1
1110
011101000000011
000010000001
0
1111111111
111011001110
001010110100100111
011001
01000110010000001000
00000001010
0001000
00000000
00100010100
111111110111
01101101111
Expected Output
0
4
0
3
0
1
0
0
0
0
0
0
4
0
2
0
1
4
4
0
4
0
4
4
1
2
1
4
3
1
3
0
1
1
6
0
0
0
0
4
1
4
2
0
4
0
3
0
0
0
1
0
0
4
5
5
1
0
5
3
0
4
2
2
2
3
1
0
3
0
4
7
0
5
0
0
1
2
2
4
0
1
0
2
2
1
0
0
0
0
3
0
0
1
0
1
0
2
5
6
2
4
0
2
3
0
3
4
1
5
2
1
0
1
2
1
0
0
0
0
4
0
3
2
4
0
1
2
0
0
1
2
0
0
0
0
2
1
1
2
0
0
0
3
0
0
2
3
2
0
4
1
1
2
1
1
3
4
0
1
3
1
2
2
0
0
4
1
1
0
1
1
0
3
2
1
0
7
2
3
0
4
2
0
0
2
0
0
0
1
2
4
1
5
0
2
4
2
0
3
0
0
2
0
1
0
1
4
4
3
5
2
3
0
2
4
0
0
5
0
0
3
5
3
0
1
0
4
1
0
3
6
0
0
0
0
1
4
1
4
2
4
2
2
2
1
4
6
6
0
2
0
4
0
1
5
1
5
2
0
4
1
2
0
0
1
0
0
2
5
1
1
1
1
0
0
1
3
4
0
5
4
0
3
3
4
3
1
4
0
0
0
0
0
0
0
0
6
1
0
3
0
2
1
0
0
0
1
1
3
1
0
4
2
0
2
0
0
5
1
0
0
2
0
4
0
2
4
2
2
1
2
2
6
0
2
1
0
2
5
4
0
0
0
2
0
0
2
0
0
1
4
3
4
4
0
3
1
1
4
0
1
5
4
0
1
2
0
3
3
3
4
0
2
2
0
3
2
1
4
1
4
0
0
2
3
2
3
1
0
4
0
7
0
1
1
0
0
0
0
1
1
0
0
3
4
1
1
0
1
1
5
2
1
1
1
0
0
2
4
4
6
2
0
0
0
2
2
6
1
0
4
5
1
3
0
1
0
0
1
3
3
2
0
0
0
2
0
0
0
3
2
1
4
1
1
2
0
3
0
0
2
0
1
1
1
1
1
1
1
4
0
0
1
4
1
0
6
1
5
5
5
0
0
0
1
3
0
0
0
3
3
1
0
5
0
3
0
2
0
2
1
0
2
1
0
2
2
3
1
1
2
6
1
3
0
1
0
0
1
0
0
0
4
0
0
4
0
3
3
3
0
1
1
0
2
2
2
4
1
1
1
6
4
0
3
4
1
2
0
4
7
1
2
2
0
6
4
0
3
3
0
1
4
0
2
4
1
2
0
3
0
2
2
1
4
2
3
0
0
1
2
4
2
0
0
2
3
3
1
2
5
1
0
1
1
2
4
0
0
5
1
3
2
1
1
0
1
3
1
4
2
1
0
6
5
3
1
2
1
1
0
0
3
0
2
3
1
0
0
4
2
1
1
0
0
3
2
3
0
1
3
3
0
0
0
2
1
0
4
3
4
1
1
1
6
1
2
1
2
0
2
0
0
5
0
2
0
0
1
0
4
0
1
0
7
5
1
4
1
1
3
0
0
0
2
3
1
3
4
5
1
1
6
0
0
2
5
2
3
0
0
0
4
0
2
2
0
0
1
0
1
3
1
1
2
2
2
0
2
5
2
1
1
3
1
2
1
0
0
0
1
3
1
1
0
0
1
1
3
1
1
0
0
0
7
0
4
1
3
1
3
2
1
3
7
3
2
1
2
1
1
2
0
0
2
4
1
1
0
0
2
5
2
2
2
1
3
1
3
4
0
0
2
1
0
0
3
4
1
2
1
0
0
1
1
2
Your Output
0
4
0
3
0
1
0
0
0
0
0
0
4
0
2
0
1
4
4
0
4
0
4
4
1
2
1
4
3
1
3
0
1
1
6
0
0
0
0
4
1
4
2
0
4
0
3
0
0
0
1
0
0
4
5
5
1
0
5
3
0
4
2
2
2
3
1
0
3
0
4
7
0
5
0
0
1
2
2
4
0
1
0
2
2
1
0
0
0
0
3
0
0
1
0
1
0
2
5
6
2
4
0
2
3
0
3
4
1
5
2
1
0
1
2
1
0
0
0
0
4
0
3
2
4
0
1
2
0
0
1
2
0
0
0
0
2
1
1
2
0
0
0
3
0
0
2
3
2
0
4
1
1
2
1
1
3
4
0
1
3
1
2
2
0
0
4
1
1
0
1
1
0
3
2
1
0
7
2
3
0
4
2
0
0
2
0
0
0
1
2
4
1
5
0
2
4
2
0
3
0
0
2
0
1
0
1
4
4
3
5
2
3
0
2
4
0
0
5
0
0
3
5
3
0
1
0
4
1
0
3
6
0
0
0
0
1
4
1
4
2
4
2
2
2
1
4
6
6
0
2
0
4
0
1
5
1
5
2
0
4
1
2
0
0
1
0
0
2
5
1
1
1
1
0
0
1
3
4
0
5
4
0
3
3
4
3
1
4
0
0
0
0
0
0
0
0
6
1
0
3
0
2
1
0
0
0
1
1
3
1
0
4
2
0
2
0
0
5
1
0
0
2
0
4
0
2
4
2
2
1
2
2
6
0
2
1
0
2
5
4
0
0
0
2
0
0
2
0
0
1
4
3
4
4
0
3
1
1
4
0
1
5
4
0
1
2
0
3
3
3
4
0
2
2
0
3
2
1
4
1
4
0
0
2
3
2
3
1
0
4
0
8
0
1
1
0
0
0
0
1
1
0
0
3
4
1
1
0
1
1
5
2
1
1
1
0
0
2
4
4
6
2
0
0
0
2
2
6
1
0
4
5
1
3
0
1
0
0
1
3
3
2
0
0
0
2
0
0
0
3
2
1
4
1
1
2
0
3
0
0
2
0
1
1
1
1
1
1
1
4
0
0
1
4
1
0
6
1
5
5
5
0
0
0
1
3
0
0
0
3
3
1
0
5
0
3
0
2
0
2
1
0
2
1
0
2
2
3
1
1
2
6
1
3
0
1
0
0
1
0
0
0
4
0
0
4
0
3
3
3
0
1
1
0
2
2
2
4
1
1
1
6
4
0
3
4
1
2
0
4
7
1
2
2
0
6
4
0
3
3
0
1
4
0
2
4
1
2
0
3
0
2
2
1
4
2
3
0
0
1
2
4
2
0
0
2
3
3
1
2
5
1
0
1
1
2
4
0
0
5
1
3
2
1
1
0
1
3
1
4
2
1
0
6
5
3
1
2
1
1
0
0
3
0
2
3
1
0
0
4
2
1
1
0
0
3
2
3
0
1
3
3
0
0
0
2
1
0
4
3
4
1
1
1
6
1
2
1
2
0
2
0
0
5
0
2
0
0
1
0
4
0
1
0
7
5
1
4
1
1
3
0
0
0
2
3
1
3
4
5
1
1
6
0
0
2
5
2
3
0
0
0
4
0
2
2
0
0
1
0
1
3
1
1
2
2
2
0
2
5
2
1
1
3
1
2
1
0
0
0
1
3
1
1
0
0
1
1
3
1
1
0
0
0
7
0
4
1
3
1
3
2
1
3
7
3
2
1
2
1
1
2
0
0
2
4
1
1
0
0
2
5
2
2
2
1
3
1
3
4
0
0
2
1
0
0
3
4
1
2
1
0
0
1
1
2
Difference
Generator Parameters
--n_high 30 --n_low 1 --t_high 1000 --t_low 1