#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
set<int> s;
//vector<int> v[100] //二元数组;
map<int,int> mp;
bool cmp(pair<int,int> a,pair<int,int> b){
    if(a.second!=b.second){
        return a.second < b.second;
    }
    return a.first < b.first;
}
//int gcd(int a,int b){//8,12
//  if(!b) return a;
//  return gcd(b,a%b);
//}
int gcd(int a,int b){
    if(!b) return a;
    return gcd(b,a%b);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //cout << 8%12 << endl;
//  for(int i = 0;i < 2;i++){
//      for(int j = 0;j < 2;j++){
//          int x;
//          cin >> x;
//          v[i].push_back(x);
//      }
//  }
//  
//  for(int i = 0;i < 2;i++){
//      for(int j = 0;j < 2;j++){
//          cout << v[i][j] ;
//      }
//  }

//  vector<int> v = {0,7,8,2,3,5};
//  
//  sort(v.begin(),v.end());
//  for(auto x:v) cout << x << endl;

//pair用法
//  vector<pair<int,int>> v={{1,2},{2,2},{3,3}};
//  sort(v.begin(),v.end(),cmp);
//  for(auto x:v) cout << x.first << " " << x.second << endl;

    //cout << endl;

//sort用法
//  sort(v.begin(),v.end(),greater<int>());
//  for(auto x:v) cout << x << endl;

//lower_bound和upper_bound用法
//  vector<int> v = {1,2,3,4,5,6};
//  int pos = lower_bound(v.begin(),v.end(),2)-v.begin();
//  int pos = lower_bound(v.begin()+2,v.end(),2)-v.begin();
//  int pos = lower_bound(v.begin(),v.end(),999)-v.begin();//如果找不到对于元素就会返回尾迭代器
//  if(pos == v.size()) cout << "No" << endl;
//  cout << pos << endl;

//  int pos = lower_bound(v.begin(),v.begin()+2,3)-v.begin();
//  if(pos == v.size()) cout << "No" << endl;
//  cout << pos << endl;

//reverse函数[,) 不包括最后一个点
//  vector<int> v = {1,2,3,4,5,6};
//  //reverse(v.begin(),v.end());
//  reverse(v.begin()+2,v.begin()+5);//2-4
//  //reverse(v.begin(),v.end()-2);
//  for(auto x:v) cout << x << endl;

//  vector<int> v = {2,3,4,4};
//  reverse(v.begin(),v.end()-1);
//  for(auto x:v) cout << x << endl;

//max,min(C++11的用法)
////    int x = max({1,2,3,4});
//  int x = min({1,2,3,4});
//  cout << x << endl;



//unique函数：先排序后去重
//  vector<int> v = {1,1,3,2,2};
//  sort(v.begin(),v.end());
//  v.erase(unique(v.begin(),v.end()),v.end());
//  for(auto x:v) cout << x << endl;

//数学函数
//  int x = pow(4,1.0/3);//4的根号3
//  cout << x << endl;
//  int x = ceil(2.1);//向上取整
//  cout << x << endl;
//  int x = floor(2.1);//向下取整
//  cout << x << endl;
//  int x = round(2.51);//四舍五入
//  cout << x << endl;
    //int x = log2(4);
//  int x = __lg(4);//int类型用这个，保证结果准确___
//  cout << x << endl;


//gcd和lcm,只有C++17以上才有直接调用gcd和lcm函数的功能
//lcm = a/gcd(a,b)*b
//  int x = gcd(8,12);
//  cout << x << endl;
//  cout << 8/x*12 << endl;

    //vector
//  vector<int> a;
//  a.push_back(1);
//  a.resize(3,2);
//  a.clear();
//  //for(auto x:a) cout << x << endl;
//  cout << a.size() << endl;

//  a.pop_back();
//  cout << a.size() << endl;


    //stack
//  stack<int> stk;
//  stk.push(1);
//  int a = stk.top();
//  stk.pop();
    //cout << a << endl;

    //queue
//  queue<int> q;
//  q.push(1);
//  int a = q.front();
//  q.pop();
//  cout << a << endl;

    //优先队列输出堆顶最大元素
//  priority_queue<int> q;
//  q.push(3);
//  q.push(1);
//  q.push(9);
//  while(q.size()){
//      int x = q.top();
//      q.pop();
//      cout << x << endl;
//  }

//  priority_queue<int,vector<int>,greater<int>> q;
//  q.push(3);
//  q.push(1);
//  q.push(9);
//  while(q.size()){
//      int x = q.top();
//      q.pop();
//      cout << x << endl;
//  }

    //队列，栈，优先队列都不能用for(auto x:q)来访问，只能访问最顶上的元素


    //set有序，不重复；multiset有序，可重复；unordered_set无序不重复
//  set<int> st;
//  //set<int,greater<int>> st;
//  st.insert(4);//因为是往set集合中间插入
//  st.insert(2);
//  st.insert(2);
//  st.insert(4);
//  for(auto x:st) cout << x << endl;
//  if(st.find(5) != st.end()) cout << "yes" << endl;
//  if(st.count(4)) cout << 1 << endl;


    //map
//  map<int,int> mp;
//  mp[1] = 2;
//  mp[2] = 3;
    //for(auto x:mp) cout << x.first << " " << x.second << endl;

    //map统计字符串的出现
//  map<string,int> mp;
//  string s[5] = {"a","a","a","b","c"};
//  for(int i = 0;i < 5;i++){
//      mp[s[i]]++;
//  }
//  for(auto x:mp) cout << x.first << " " << x.second << endl;

//  string s = "afcbkfvbf";
//  string a = s.substr(2,3);//substr(开始子串，子串长度)
//  cout << a << endl;  
//  int pos = s.find("aaa");
//  if(pos != string::npos) cout << "yes" << endl;
//  int x = stoi(s);
//  cout << x << endl;




    return 0;
}