#ifndef C___FILES_DEFINE_H
#define C___FILES_DEFINE_H

// About what does this file consist or include
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
// Used namespaces
using namespace std;
using namespace __gnu_pbds;
// Definitions of shorted codes
#define vec vector
#define pb push_back
#define int long long
#define mmap multimap
#define mset multiset
#define eb emplace_back
typedef deque<int> deki;
typedef vector<int> veki;
typedef queue<int> kuint;
typedef deque<char> dekch;
#define code signed main()
#define endi cout << "\n";
#define no cout << "NO\n";
#define double long double
#define umap unordered_map
#define uset unordered_set
typedef queue<char> kuchar;
typedef vector<char> vekch;
#define scan1(n) scanf("%lld" , &n)
#define sr(a) sort(all(a))
#define yes cout << "YES\n";
#define ummap unordered_multimap
#define umset unordered_multiset
#define all(v) (v).begin() , (v).end()
#define mx_elem(v) *max_element(all(v))
#define mn_elem(v) *min_element(all(v))
#define sum_arr(v) accumulate(all(v), 0)
#define rall(v) (v).rbegin() , (v).rend()
#define cinarr(a) for (auto& x : a)cin >> x;
#define up_bnd(v , i) upper_bound(all(v) , i)
#define low_bnd(v , i) lower_bound(all(v) , i)
#define fill(v , i) fill(v.begin() , v.end() , i)
#define coutar(a) for (auto& x : a)cout << x << " ";
#define erall(v) (v).erase(unique(all((v))), (v).end());
#define io() ios_base::sync_with_stdio(false); {cin.tie(nullptr); cout.tie(nullptr);}
#define indexed_set tree<int , null_type , less<int> , rb_tree_tag , tree_order_statistics_node_update>
#define inter_set(s1 , s2 , v) set_intersection(s1.begin() , s1.end() , s2.begin() , s2.end() , back_inserter(v))
//Constants and some of helpful functions
const int inf = 1e9, mod = 1e9 + 7 , N = 1e5 + 5;
// Printing __int128 big number
void print(__int128 x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) print(x / 10);
    putchar(x % 10 + '0');
}
// GCD and LCM
int gcd(int a , int b){
    if (!(a * b))return max(a , b);
    return gcd(b , a % b);
}
int lcm(int a , int b){
    return a / gcd(a , b) * b;
}
// Finding power with binary recursion
int binpow(int a , int n){
    if (n == 0)return 1;
    if (n & 1) return a * binpow(a , n - 1);
    else{
        int c = binpow(a , n / 2);
        return c * c;
    }
}
// Checking if a number is prime or composite?
bool prime(int a){
    if (a <= 1)return false;
    for (int i = 2; i * i <= a; i++)
        if(!(a % i))return false;
    return true;
}
void shuff_arr(vec<int> a){
    minstd_rand shuff;
    shuffle(all(a) , shuff);
}
// Finding count of digits of a number
int dig_cnt(int n){
    return floor(log10(n)) + 1;
}
// Checking is a number even or not?
bool even(int n){
    return (n & 1) == 0;
}
// Checking are two points intersect?
int orient(int px, int py, int qx, int qy, int rx, int ry) {
  int val = (qy - py) * (rx - qx) - (qx - px) * (ry - py);
  if (val == 0) return 0;
  return (val > 0) ? 1 : 2;
}
bool kesilish(int p1x, int p1y, int p2x, int p2y, int q1x, int q1y, int q2x, int q2y) {
  int o1 = orient(p1x, p1y, p2x, p2y, q1x, q1y);
  int o2 = orient(p1x, p1y, p2x, p2y, q2x, q2y);
  int o3 = orient(q1x, q1y, q2x, q2y, p1x, p1y);
  int o4 = orient(q1x, q1y, q2x, q2y, p2x, p2y);
  if (o1 != o2 && o3 != o4) return true;
  return false;
}
#endif //C___FILES_DEFINE_H