#define C " "
#define O( _ ) # _
#define R( n , d ) e ( n , d )
#define e(p,o)o##p
#define D O ( % ) O ( l ) O ( d )
#define U R ( e ( g , n ) , e ( o , l ) )
#define M H ( R ( e ( c , i ) , t ) , R ( e ( a , t ) , s ) )
#define P H ( R ( e ( f , t ) , n ) , R ( e ( i , r ) , p ) ) (
#define H(O,r)R(O,r)
#include<stdio.h>
	H ( R ( 	e ( f , 	e ) , e 	( d , e
)	) , R	(	e ( p	,	y ) ,	t	) ) H
( R	( e	( t	, c	) ,	u )	, R	( e
( r ,	t	) , s	)	) { U	n	, t ;	}
F ; H ( 	R ( e ( 	f , e ) 	, e ( d
, e )	)	, R (	e	( p ,	y	) , t	)
) H	( R	( e	( d	, e	) ,	e (	n ,
g	) ) ,	R	( e (	i	, s )	,	e ( n
	, u ) ) 	) U B ; 	M F I [ 	4 * 5 ]
,	w [ 4	*	5 ] ,	p	[ 4 ]	=	{ { 9
, 1	} ,	{ 1	, 1	} ,	{ 1	, 1	} ,
{ 6 *	7	, 1 }	}	; M R	(	e ( t	,
n ) , i 	) J ; M 	R ( e ( 	d , i )
, e (	o	, v )	)	o ( F	f	) { e	(
f ,	i )	( f	. t	- 1	) {	J =	P D
O	( / )	D	, f .	n	, f .	t	) ; }
	R ( e ( 	e , s ) 	, e ( l 	, e ) )
{	J = P	D	, f .	n	) ; }	}	M R (
e (	d ,	i )	, e	( o	, v	) )	n (
F * f	)	{ U a	=	( * f	)	. n ,	b
= ( * f 	) . t ; 	e ( f , 	i ) ( b
) { H	(	R ( e	(	e , l	)	, i )	,
e (	h ,	w )	) (	a )	{ U	i =	b %
a	; b =	a	; a =	i	; } b	=	b < 0
	? - b : 	b ; ( * 	f ) . n 	e ( = ,
/	) b ;	(	* f )	.	t e (	=	, / )
b ;	} }	R (	e (	t ,	n )	, i	) R
( e (	n	, i )	,	e ( a	,	m ) )	(
R ( e ( 	t , n ) 	, i ) a 	, R ( e
( r ,	a	) , e	(	h , c	)	) * v	[
] )	{ B	m ,	W ;	R (	e (	t ,	n )
,	i ) i	,	c ; R	(	e ( r	,	o ) ,
	f ) ( i 	= 1 ; i 	< 5 ; i 	= i + 1
)	{ e (	f	, i )	(	a > i	)	{ J =
H (	R (	e (	f ,	n )	, a	) ,	R (
e ( c	,	s ) ,	s	) ) (	v	[ i ]	,
D O ( / 	) D , & 	p [ i - 	1 ] . n
, & p	[	i - 1	]	. t )	;	} n (	p
+ i	- 1	) ;	} I	[ 0	] =	p [	1 ]
;	R ( e	(	r , o	)	, f )	(	i = 0
	; i < p 	[ 0 ] . 	n ; i = 	i + 1 )
{	I [ i	+	1 ] .	n	= I [	i	] . n
* p	[ 2	] .	t +	p [	2 ]	. n	* I
[ i ]	.	t ; I	[	i + 1	]	. t =	I
[ i ] . 	t * p [ 	2 ] . t 	; n ( I
+ i +	1	) ; }	R	( e (	r	, o )	,
f )	( W	= ~	( ~	0 e	( <	, <	) p
[	0 ] .	n	* 2 )	;	~ ( B	)	0 - W
	; W = W 	- 1 ) { 	w [ c = 	0 ] = I
[	0 ] ;	R	( e (	r	, o )	,	f ) (
m =	W ,	i =	1 ;	! (	i >	p [	0 ]
. n )	;	i = i	+	1 , m	=	m / 4	)
{ e ( f 	, i ) ( 	( m & 3 	) < 2 )
{ e (	f	, i )	(	m & 1	)	{ w [	c
] .	n e	( =	, *	) I	[ i	] .	t ;
e	( f ,	i	) ( (	w	[ c ]	.	t e (
	= , * ) 	I [ i ] 	. n ) < 	0 ) { w
[	c ] .	n	e ( =	,	* ) -	1	; w [
c ]	. t	e (	= ,	* )	- 1	; }	} R
( e (	e	, s )	,	e ( l	,	e ) )	{
w [ c ] 	. n e ( 	= , * ) 	I [ i ]
. n ;	w	[ c ]	.	t e (	=	, * )	I
[ i	] .	t ;	} }	R (	e (	e ,	s )
,	e ( l	,	e ) )	{	w [ c	=	c + 1
	] = I [ 	i ] ; } 	} R ( e 	( r , o
)	, f )	(	m = W	,	i = c	=	0 ; i
< p	[ 0	] .	n ;	i =	i +	1 ,	m =
m / 4	)	{ e (	f	, i )	(	( m &	3
) > 1 ) 	{ w [ 0 	] . n = 	w [ 0 ]
. n *	w	[ c +	1	] . t	+	( ( m	&
1 )	? -	1 :	+ 1	) *	w [	c +	1 ]
.	n * w	[	0 ] .	t	; w [	0	] . t
	= w [ 0 	] . t * 	w [ c = 	c + 1 ]
.	t ; }	}	n ( w	)	; e (	f	, i )
( !	p [	3 ]	. t	e (	| ,	| )	( !
( p [	3	] . n	-	w [ 0	]	. n )	e
( & , & 	) ! ( p 	[ 3 ] . 	t - w [
0 ] .	t	) ) )	{	R ( e	(	r , o	)
, f	) (	m =	W ,	i =	0 ;	i <	p [
0	] . n	;	i = i	+	1 , m	=	m / 4
	) { o ( 	I [ i ] 	) ; J = 	P C O (
%	) O (	c	) C ,	O	( * )	O	( / )
O (	+ )	O (	- )	[ m	& 3	] )	; }
o ( I	[	i ] )	;	J = P	C	O ( =	)
C ) ; o 	( w [ 0 	] ) ; J 	= P O (
% ) O	(	c ) ,	e	( 0 ,	1	) ) ;	}
} H	( R	( e	( n	, r	) ,	u )	, R
(	e ( t	,	e ) ,	r	) ) J	-	1 ; }