救救孩子吧呜呜呜呜呜呜。

https://www.luogu.com.cn/record/99387212 https://www.luogu.com.cn/record/99393292

#include <bits/stdc++.h>
using namespace std ;

#define int unsigned long long
const int N = 250005 ;

int read ( ) {
	char ch = getchar ( ) ;
	int x = 0 ;
	while ( ch < '0' || ch > '9' )
		ch = getchar ( ) ;
	while ( ch >= '0' && ch <= '9' )
		x = x * 10 + ch - 48 , ch = getchar ( ) ;
	return x ;
}

int n , m , a[N] , b[N] , ans[N] ;
int sta[N] , tpa , stb[N] , tpb ;

struct Node {
	int l , r , id ;
} p[N] ;

bool cmp ( Node u , Node v ) {
	return u .r < v .r ;
}

struct Mat {
	int n , m , w[5][5] ;
	Mat ( int _n = 5 , int _m = 5 ) :
		n ( _n ) , m ( _m ) { memset ( w , 0 , sizeof ( w ) ) ; }
//	int *operator [] ( int x ) { return w [ x ] ; }
	
	void init ( ) { for ( int i = 0 ; i < 5 ; ++ i ) w [ i ] [ i ] = 1 ; }
	
	friend Mat operator * ( Mat u , Mat v ) {
		Mat z ( u .n , v .m ) ;
		for ( int i = 0 ; i < u .n ; ++ i )
			for ( int j = 0 ; j < v .m ; ++ j )
				for ( int k = 0 ; k < u .m ; ++ k )
					if ( u .w [ i ] [ k ] && v .w [ k ] [ j ] )
						z .w [ i ] [ j ] += u .w [ i ] [ k ] * v .w [ k ] [ j ] ;
		return z ;
	}
	
} t[N<<2] , lz[N<<2] , I ;

bool tg[N<<2] ;

Mat mak1 ( int k ) {
	Mat ret ; ret .init ( ) ;
	ret .w [ 1 ] [ 1 ] = 0 , ret .w [ 0 ] [ 1 ] = k ;
	return ret ;
}

Mat mak2 ( int k ) {
	Mat ret ; ret .init ( ) ;
	ret .w [ 2 ] [ 2 ] = 0 , ret .w [ 0 ] [ 2 ] = k ;
	return ret ;
}

Mat mak3 ( int k ) {
	Mat ret ; ret .init ( ) ;
	ret .w [ 3 ] [ 3 ] = 0 , ret .w [ 0 ] [ 3 ] = k ;
	return ret ;
}

Mat mak4 ( int k ) {
	Mat ret ; ret .init ( ) ;
	ret .w [ 3 ] [ 3 ] = 0 , ret .w [ 1 ] [ 3 ] = k ;
	return ret ;
}

Mat mak5 ( int k ) {
	Mat ret ; ret .init ( ) ;
	ret .w [ 3 ] [ 3 ] = 0 , ret .w [ 2 ] [ 3 ] = k ;
	return ret ;
}

Mat mak6 ( ) {
	Mat ret ; ret .init ( ) ; ret .w [ 3 ] [ 4 ] = 1 ;
	return ret ;
}

void build ( int k , int l , int r ) {
	t [ k ] .n = 1 ;
	t [ k ] .w [ 0 ] [ 0 ] = r - l + 1 ;
	lz [ k ] = I ;
	if ( l == r ) return ;
	int mid = ( l + r ) >> 1 ;
	build ( k << 1 , l , mid ) ;
	build ( k << 1 | 1 , mid + 1 , r ) ;
}

void pushdown ( int k ) {
	if ( tg [ k ] ) {
		t [ k << 1 ] = t [ k << 1 ] * lz [ k ] ;
		t [ k << 1 | 1 ] = t [ k << 1 | 1 ] * lz [ k ] ;
		lz [ k << 1 ] = lz [ k << 1 ] * lz [ k ] ;
		lz [ k << 1 | 1 ] = lz [ k << 1 | 1 ] * lz [ k ] ;
		lz [ k ] = I ;
		tg [ k << 1 ] = tg [ k << 1 | 1 ] = 1 ;
		tg [ k ] = 0 ;
	}
}

void pushup ( int k ) {
	for ( int i = 1 ; i < 5 ; ++ i )
		t [ k ] .w [ 0 ] [ i ] = t [ k << 1 ] .w [ 0 ] [ i ] + t [ k << 1 | 1 ] .w [ 0 ] [ i ] ;
}

void change ( int k , int l , int r , int x , int y , Mat z ) {
	if ( x <= l && r <= y ) {
		t [ k ] = t [ k ] * z ;
		lz [ k ] = lz [ k ] * z ;
		tg [ k ] = 1 ;
		return ;
	}
	pushdown ( k ) ;
	int mid = ( l + r ) >> 1 ;
	if ( x <= mid ) change ( k << 1 , l , mid , x , y , z ) ;
	if ( y > mid ) change ( k << 1 | 1 , mid + 1 , r , x , y , z ) ;
	pushup ( k ) ;
}

int query ( int k , int l , int r , int x , int y ) {
	if ( x <= l && r <= y )
		return t [ k ] .w [ 0 ] [ 4 ] ;
	pushdown ( k ) ;
	int mid = ( l + r ) >> 1 ;
	if ( y <= mid ) return query ( k << 1 , l , mid , x , y ) ;
	if ( x > mid ) return query ( k << 1 | 1 , mid + 1 , r , x , y ) ;
	return query ( k << 1 , l , mid , x , y ) + query ( k << 1 | 1 , mid + 1 , r , x , y ) ;
}

signed main ( ) {
//	freopen ( "match.in" , "r" , stdin ) ;
//	freopen ( "match18.in" , "r" , stdin ) ;
	freopen ( "match16.in" , "r" , stdin ) ;
	freopen ( "match.out" , "w" , stdout ) ;
	int TT = read ( ) ;
	n = read ( ) ;
	for ( int i = 1 ; i <= n ; ++ i )
		a [ i ] = read ( ) ;
	for ( int i = 1 ; i <= n ; ++ i )
		b [ i ] = read ( ) ;
	m = read ( ) ;
	for ( int i = 1 ; i <= m ; ++ i )
		p [ i ] .l = read ( ) , p [ i ] .r = read ( ) , p [ i ] .id = i ;
	sort ( p + 1 , p + 1 + m , cmp ) ;
	I .init ( ) ;
	build ( 1 , 1 , n ) ;
	change ( 1 , 1 , n , 1 , 1 , mak1 ( a [ 1 ] ) * mak2 ( b [ 1 ] ) * mak3 ( a [ 1 ] * b [ 1 ] ) * mak6 ( ) ) ;
	
	int j = 1 ;
	while ( j <= m && p [ j ] .r == 1 ) ans [ p [ j ] .id ] = a [ 1 ] * b [ 1 ] , ++ j ;
	sta [ tpa = 1 ] = 1 ;
	stb [ tpb = 1 ] = 1 ;
	for ( int i = 2 ; i <= n ; ++ i ) {
		while ( tpa && a [ sta [ tpa ] ] < a [ i ] ) -- tpa ;
		while ( tpb && b [ stb [ tpb ] ] < b [ i ] ) -- tpb ;
		Mat ai = mak1 ( a [ i ] ) , bi = mak2 ( b [ i ] ) ;
		if ( sta [ tpa ] == stb [ tpb ] ) {
			int x = sta [ tpa ] + 1 ;
			change ( 1 , 1 , n , x , i , mak3 ( a [ i ] * b [ i ] ) * ai * bi ) ;
		}
		else if ( sta [ tpa ] > stb [ tpb ] ) {
			int x = sta [ tpa ] + 1 , y = stb [ tpb ] + 1 ;
			change ( 1 , 1 , n , x , i , mak3 ( a [ i ] * b [ i ] ) * ai * bi ) ;
			change ( 1 , 1 , n , y , x - 1 , mak4 ( b [ i ] ) * bi ) ;
		}
		else {
			int x = stb [ tpb ] + 1 , y = sta [ tpa ] + 1 ;
			change ( 1 , 1 , n , x , i , mak3 ( a [ i ] * b [ i ] ) * ai * bi ) ;
			change ( 1 , 1 , n , y , x - 1 , mak5 ( a [ i ] ) * ai ) ;
		}
		change ( 1 , 1 , n , 1 , n , mak6 ( ) ) ;
		sta [ ++ tpa ] = i ;
		stb [ ++ tpb ] = i ;
		while ( j <= m && p [ j ] .r == i )
			ans [ p [ j ] .id ] = query ( 1 , 1 , n , p [ j ] .l , p [ j ] .r ) , ++ j ;
	}
	for ( int i = 1 ; i <= m ; ++ i )
		cout << ans [ i ] << '\n' ;
	return 0 ;
}