#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define ll long long
#define pb push_back
#define s second
#define f first
#define pf push_front
#define inf 100000000000000000
#define bitebi __builtin_popcountll
#define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
#define YES cout <<"YES\n"
#define NO cout << "NO\n"
#define debug cout << "Here Fine" << endl ;
#define pr pair < int , int >
#define fbo find_by_order // returns iterator
#define ook order_of_key // returns strictly less numbers than key
using namespace std ;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
const double Pi=acos(-1.0);
const double EPS=1E-8;
const int mod = 1000000007 ;
const int mod1 = 998244353 ;
const int N = 4e5 + 10 ;
mt19937 R(time(0));
map < int , int > ma , ma1 ;
#include "werewolf.h"
int n , pp[ N ] , ss[ N ] ;
vector < int > V[ N ] , v[ 2 ][ N ] ;
// DSU
void create( int node ){
pp[ node ] = node ;
ss[ node ] = 1 ; return ;
}
int find( int node ){
if( pp[ node ] == node ) return node ;
return pp[ node ] = find( pp[ node ] ) ;
}
void unite( int a , int b ){
if( ss[ a ] < ss[ b ] ) swap( a , b ) ;
if( ss[ a ] == ss[ b ] ) ss[ a ] ++ ;
pp[ b ] = a ; return ;
}
// Build the trees
int cnt = n + 1 ;
int app[ 2 ][ N ] ;
void ad( int u , int tp ){
create( cnt ) ;
app[ tp ][ u ] = u ;
app[ tp ][ cnt ] = u ;
set < int > se ;
se.insert( find( u ) ) ;
for( auto x : V[ u ] ){
if( x > u && tp == 0 ) continue ;
if( x < u && tp == 1 ) continue ;
se.insert( find( x ) ) ;
}
for( auto x : se ){
v[ tp ][ cnt ].pb( x ) ;
v[ tp ][ x ].pb( cnt ) ;
unite( x , find( cnt ) ) ;
}
int x = find( cnt ) ;
pp[ x ] = cnt ; pp[ cnt ] = cnt ;
ss[ cnt ] = ss[ x ] ;
cnt ++ ;
return ;
}
// now go over those trees and calculate some useful stuff
int p[ 2 ][ N ][ 20 ] , xx[ 20 ] , nmb[ 2 ][ N ] , timer = 1 , uno[ 2 ][ N ] ;
pair < int , int > lr[ 2 ][ N ] ;
pair < int , int > dfs( int node , int parent , int tp , int h ){
p[ tp ][ node ][ 0 ] = parent ;
for( int j = 1 ; j < 20 ; j ++ ){
if( xx[ j ] > h ) p[ tp ][ node ][ j ] = -1 ;
else p[ tp ][ node ][ j ] = p[ tp ][ p[ tp ][ node ][ j - 1 ] ][ j - 1 ] ;
}
pair < int , int > pp = { INT_MAX , -1 } ;
if( node <= n ){
uno[ tp ][ timer ] = node ;
nmb[ tp ][ node ] = timer ;
pp = { timer , timer } ;
timer ++ ;
}
for( auto x : v[ tp ][ node ] ){
if( x == parent ) continue ;
pair < int , int > pu ;
pu = dfs( x , node , tp , h + 1 ) ;
pp.f = min( pp.f , pu.f ) ;
pp.s = max( pp.s , pu.s ) ;
}
lr[ tp ][ node ] = pp ;
return pp ;
}
// now how find useful parent of each of the important nodes in two trees
int check( int tp , int cur , int nd ){
if( cur == -1 ) return -1 ;
if( tp == 0 && app[ tp ][ cur ] > nd ) return -1 ;
if( tp == 1 && app[ tp ][ cur ] < nd ) return -1 ;
return 1 ;
}
int find_node( int node , int tp , int nd ){
for( int j = 19 ; j >= 0 ; j -- ){
if( check( tp , p[ tp ][ node ][ j ] , nd ) == 1 )
node = p[ tp ][ node ][ j ] ;
}
if( check( tp , p[ tp ][ node ][ 0 ] , nd ) == 1 ) return p[ tp ][ node ][ 0 ] ;
return node ;
}
// now seg trees
int node[ 4 * N ] ;
void upd( int v , int vl , int vr , int pos ){
if( vl == vr ){
node[ v ] = 1 ; return ;
}
int vm = ( vl + vr ) / 2 ;
if( vm >= pos ) upd( v + v , vl , vm , pos ) ;
else upd( v + v + 1 , vm + 1 , vr , pos ) ;
node[ v ] = node[ v + v ] + node[ v + v + 1 ] ;
return ;
}
int get( int v , int vl ,int vr , int l , int r ){
if( l > r ) return 0 ;
if( vl == l && vr == r ){
return node[ v ] ;
}
int vm = ( vl + vr ) / 2 ;
int a = get( v + v , vl , vm , l , min( r , vm ) ) ;
int b = get( v + v + 1 , vm + 1 , vr , max( vm + 1 , l ) , r ) ;
return ( a + b ) ;
}
vector < int > del[ N ] , add[ N ] ;
int pas[ N ] ;
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R){
xx[ 0 ] = 1 ;
for( int j = 1 ; j < 20 ; j ++ ) xx[ j ] = xx[ j - 1 ] * 2 ;
FOR( i , X.size() ){
X[ i ] ++ ; Y[ i ] ++ ;
V[ X[ i ] ].pb( Y[ i ] ) ;
V[ Y[ i ] ].pb( X[ i ] ) ;
}
n = N ;
// build first tree
for( int j = 1 ; j <= 2 * n + 5 ; j ++ ) create( j ) ;
cnt = n + 1 ;
for( int j = 1 ; j <= n ; j ++ ){
ad( j , 0 ) ;
}
timer = 1 ;
dfs( cnt - 1 , -1 , 0 , 0 ) ;
// build second tree
for( int j = 1 ; j <= 2 * n ; j ++ ) create( j ) ;
cnt = n + 1 ;
for( int j = n ; j >= 1 ; j -- ){
ad( j , 1 ) ;
}
timer = 1 ;
dfs( cnt - 1 , -1 , 1 , 0 ) ;
// now build calculate answer part
FOR( i , S.size() ){
S[ i ] ++ ; R[ i ] ++ ; L[ i ] ++ ; E[ i ] ++ ;
int node = find_node( S[ i ] , 1 , L[ i ] ) ;
int l , r ;
l = lr[ 1 ][ node ].f ;
r = lr[ 1 ][ node ].s ;
del[ l - 1 ].pb( i ) ;
add[ r ].pb( i ) ;
}
for( int j = 1 ; j <= n ; j ++ ){
int node = uno[ 1 ][ j ] ;
upd( 1 , 1 , n , nmb[ 0 ][ node ] ) ;
for( auto x : del[ j ] ){
int node = find_node( E[ x ] , 0 , R[ x ] ) ;
int l , r ;
l = lr[ 0 ][ node ].f ;
r = lr[ 0 ][ node ].s ;
pas[ x ] -= get( 1 , 1 , n , l , r ) ;
}
for( auto x : add[ j ] ){
int node = find_node( E[ x ] , 0 , R[ x ] ) ;
int l , r ;
l = lr[ 0 ][ node ].f ;
r = lr[ 0 ][ node ].s ;
// cout << E[ x ] << " " << R[ x ] << " " << l << " " << r << " nd "<< node << endl ;
pas[ x ] += get( 1 , 1 , n , l , r ) ;
}
}
vector < int > ans ;
FOR( i , S.size() ){
if( pas[ i ] > 0 ) ans.pb( 1 ) ;
else ans.pb( 0 ) ;
}
return ans ;
}
//
// namespace {
//
// int read_int() {
// int x;
// if (scanf("%d", &x) != 1) {
// fprintf(stderr, "Error while reading input\n");
// exit(1);
// }
// return x;
// }
//
// } // namespace
//
// int main() {
// int N = read_int();
// int M = read_int();
// int Q = read_int();
// std::vector<int> X(M), Y(M), S(Q), E(Q), L(Q), R(Q);
// for (int j = 0; j < M; ++j) {
// X[j] = read_int();
// Y[j] = read_int();
// }
// for (int i = 0; i < Q; ++i) {
// S[i] = read_int();
// E[i] = read_int();
// L[i] = read_int();
// R[i] = read_int();
// }
//
// std::vector<int> A = check_validity(N, X, Y, S, E, L, R);
// for (size_t i = 0; i < A.size(); ++i) {
// printf("%d\n", A[i]);
// }
// return 0;
// }
