CSES - Shared codeLink to this code: https://cses.fi/paste/c295361ec8a64ad822a528/
/\
/\
u\
<\
T\
>\
l\
i\
k\
e\
R\
u\
s\
t
#\
i\
n\
c\
l\
u\
d\
e\
<\
b\
i\
t\
s\
/\
s\
t\
d\
c\
+\
+\
.\
h\
>
u\
s\
i\
n\
g
n\
a\
m\
e\
s\
p\
a\
c\
e
s\
t\
d
;
u\
s\
i\
n\
g
u\
3\
2
=
u\
i\
n\
t\
3\
2\
_\
t
;
u\
s\
i\
n\
g
u\
6\
4
=
u\
i\
n\
t\
6\
4\
_\
t
;
u\
s\
i\
n\
g
u\
1\
2\
8
=
_\
_\
u\
i\
n\
t\
1\
2\
8\
_\
t
;
c\
o\
n\
s\
t
i\
n\
t
I
=
2\
0
<\
<
2\
0,
O
=
1\
0;
i\
n\
t
_\
i\
0,
_\
o\
0;
c\
h\
a\
r
_
,
_\
i
[
I
]
,
_\
o
[
O
]
;
i\
n\
l\
i\
n\
e
v\
o\
i\
d
r\
e\
a\
d
(
c\
h\
a\
r
&
c
)
{
w\
h\
i\
l\
e
(
(
c
=
_\
i
[
_\
i\
0
+\
+
]
)
<\
=
3\
2
)
;
}
t\
e\
m\
p\
l\
a\
t\
e
<
t\
y\
p\
e\
n\
a\
m\
e
T
>
i\
n\
l\
i\
n\
e
v\
o\
i\
d
r\
e
(
T
&
x
)
{
f\
o\
r
(
x
=
_\
i
[
_\
i\
0
+\
+
]
^
4\
8
;
(
_
=
_\
i
[
_\
i\
0
+\
+
]
)
&
1\
6
;
x
=
x
*
1\
0
+
(
_
^
4\
8
)
)
;
}
t\
e\
m\
p\
l\
a\
t\
e
<
t\
y\
p\
e\
n\
a\
m\
e
T
>
i\
n\
l\
i\
n\
e
v\
o\
i\
d
w\
r
(
T
x
)
{
c\
h\
a\
r
s
[
1\
1
]
;
i\
n\
t
i
=
0
;
d\
o
s
[
i
+\
+
]
=
'\
0\
'
+
x
%
1\
0
,
x
/\
=
1\
0
;
w\
h\
i\
l\
e
(
x
)
;
w\
h\
i\
l\
e
(
i
-\
-
)
_\
o
[
_\
o\
0
+\
+
]
=
s
[
i
]
;
_\
o
[
_\
o\
0
+\
+
]
=
3\
2
;
}
c\
o\
n\
s\
t
u\
3\
2
M\
O\
D
=
1\
0\
0\
0\
0\
0\
0\
0\
0\
7
;
c\
o\
n\
s\
t
s\
i\
z\
e\
_\
t
m\
a\
x\
n
=
1\
0\
2
;
u\
1\
2\
8
d\
p
[
m\
a\
x\
n
]
,
n\
d\
p
[
m\
a\
x\
n
]
;
i\
n\
t
m\
a\
i\
n
(
)
{
s\
i\
z\
e\
_\
t
I\
N\
P
=
f\
r\
e\
a\
d
(
_\
i
,
1
,
I
,
s\
t\
d\
i\
n
)
;
a\
s\
s\
e\
r\
t
(
I\
N\
P
>
0
)
;
s\
i\
z\
e\
_\
t
N
,
M
;
u\
3\
2
a
;
r\
e
(
N
)
,
r\
e
(
M
)
;
r\
e
(
a
)
;
i\
f
(
a
=\
=
0
)
{
f\
o\
r
(
s\
i\
z\
e\
_\
t
j
=
1
;
j
<\
=
M
;
+\
+
j
)
{
d\
p
[
j
]
=
1
;
}
}
e\
l\
s\
e
{
d\
p
[
a
]
=
1
;
}
f\
o\
r
(
s\
i\
z\
e\
_\
t
i
=
1
;
i
<
N
;
+\
+
i
)
{
f\
o\
r
(
s\
i\
z\
e\
_\
t
j
=
1
;
j
<\
=
M
;
+\
+
j
)
n\
d\
p
[
j
]
=
0
;
r\
e
(
a
)
;
i\
f
(
a
=\
=
0
)
{
f\
o\
r
(
s\
i\
z\
e\
_\
t
j
=
1
;
j
<\
=
M
;
+\
+
j
)
{
n\
d\
p
[
j
]
=
(
d\
p
[
j
-
1
]
+
d\
p
[
j
]
+
d\
p
[
j
+
1
]
)
;
}
}
e\
l\
s\
e
{
n\
d\
p
[
a
]
=
(
d\
p
[
a
-
1
]
+
d\
p
[
a
]
+
d\
p
[
a
+
1
]
)
;
}
i\
f
(
i
%
6\
0
=\
=
0
)
{
f\
o\
r
(
s\
i\
z\
e\
_\
t
j
=
1
;
j
<\
=
M
;
+\
+
j
)
d\
p
[
j
]
=
n\
d\
p
[
j
]
%
M\
O\
D
;
}
e\
l\
s\
e
{
f\
o\
r
(
s\
i\
z\
e\
_\
t
j
=
1
;
j
<\
=
M
;
+\
+
j
)
d\
p
[
j
]
=
n\
d\
p
[
j
]
;
}
}
u\
1\
2\
8
S
=
0
;
f\
o\
r
(
s\
i\
z\
e\
_\
t
j
=
1
;
j
<\
=
M
;
+\
+
j
)
S
=
(
S
+
d\
p
[
j
]
)
%
M\
O\
D
;
w\
r
(
S
)
;
f\
w\
r\
i\
t\
e
(
_\
o
,
1
,
_\
o\
0
,
s\
t\
d\
o\
u\
t
)
;
}
/\
/\
1\
0\
0\
0\
l\
i\
n\
e\
s\
n\
i\
c\
e\
r\
o\
u\
n\
d\
n\
u\
m\
b\
e\
r\
:\
-\
P