//
//#define _CRT_SECURE_NO_WARNINGS
////#include <iostream>
////#include <vector>
//#include <stack>
//#include <memory>
//#include <string>
//#include <iostream>
//#include <vector>
//using namespace std;
//#define MIN -0x3f3f3f3f
//
//
//int maxProfit(vector<int>&& prices) {
//    int n = prices.size();
//    vector<vector<int>>f(n, vector<int>(3, MIN));
//    vector<vector<int>>g(n, vector<int>(3, MIN));
//    f[0][0] = -prices[0];
//    g[0][0] = 0;
//    for (int i = 1; i < n; ++i)
//    {
//        for (int j = 0; j < 3; ++j)
//        {
//            f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
//            g[i][j] = g[i - 1][j];
//            if (j - 1 >= 0)
//                g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);
//        }
//    }
//
//    int ret = 0;
//    for (int j = 0; j < 3; ++j)
//    {
//        ret = max(ret, g[n - 1][j]);
//    }
//    return ret;
//}
//int binInsert(int n, int m, int j, int i) {
//    vector<int> vbit(32, 0);
//    int left = max(j, i);
//    int right = min(j, i);
//    int index = 0;
//    for ( ;right<=left;right++)
//    {
//        vbit[right] = (bool)(m & 1 << index);
//        ++index;
//    }
//
//
//
//    return n;
//}
//#include <iostream>
//using namespace std;
//
//bool is_ss(int num)
//{
//    if (num == 2)
//    {
//        return true;
//    }
//    for (int i = 2; i < num; ++i)
//    {
//        if (num % i == 0)
//        {
//            return false;
//        }
//    }
//    return true;
//}
//
//class A
//{
//public:
//    int a = 0;
//};
//
//int main() {
//    A*ptr=(A*)alloca(10*sizeof(A));
//    //int tmp = num / 2;
//    //while (1) 
//    //{
//    //    if (!is_ss(tmp))
//    //    {
//    //        ++tmp;
//    //        continue;
//    //    }
//    //    int s = num - tmp;
//    //    if (is_ss(s))
//    //    {
//    //        cout << tmp << endl << s << endl;
//    //        return 0;
//    //    }
//    //}
//    return 0;
//}
//// 64 λ printf("%lld")
//
////int getLCA(int a, int b) 
////{
////    stack<int> sta;
////    stack<int> stb;
////    while (a >= 1)
////    {
////        sta.push(a);
////        a /= 2;
////    }
////    while (b >= 1)
////    {
////        stb.push(b);
////        b /= 2;
////    }
////    stack<int> statmp;
////    stack<int> stbtmp;
////    while (!sta.empty())
////    {
////        statmp.push(sta.top());
////        sta.pop();
////    }
////    while (!stb.empty())
////    {
////        stbtmp.push(stb.top());
////        stb.pop();
////    }
////    while (stbtmp.size() > statmp.size())
////    {
////        stbtmp.pop();
////    }
////    while (stbtmp.size() < statmp.size())
////    {
////        statmp.pop();
////    }
////    while (1)
////    {
////        if (statmp.top() == stbtmp.top())
////        {
////            return statmp.top();
////        }
////        statmp.pop();
////        stbtmp.pop();
////        if (statmp.empty())
////            break;
////    }
////    return 0;
////}
////class A
////{
////public:
////    static void func()
////    {
////        A a;
////    }
////private:
////    A() {}
////    ~A() {}
////};
////
////int maxProfit(vector<int>&& nums) {
////    // int n=prices.size();
////    // vector<vector<int>>f(n,vector<int>(3,MIN));
////    // vector<vector<int>>g(n,vector<int>(3,MIN));
////    // f[0][0]=-prices[0];
////    // g[0][0]=0;
////    // for(int i= 1;i<n;++i)
////    // {
////    //     for(int j=0;j<3;++j)
////    //     {
////    //         f[i][j]=max(f[i-1][j],g[i-1][j]-prices[i]);
////    //         g[i][j]=g[i-1][j];
////    //         if(j-1>=0)
////    //             g[i][j]=max(g[i][j],f[i-1][j-1]+prices[i]);
////    //     }
////    // }
////
////    // int ret=0;
////    // for(int j=0;j<3;++j)
////    // {
////    //     ret=max(ret,g[n-1][j]);
////    // }
////    // retur n ret;
////
////    int start = 0;
////    int end = 0;
////    vector<int> vprice;
////    int ret = 0;
////    while (end < nums.size() - 1)
////    {
////        while (end < nums.size() - 1 && nums[end] < nums[end + 1])
////        {
////            ++end;
////        }
////        int sum = nums[end] - nums[start];
////        if (sum > 0)
////        {
////            vprice.push_back(sum);
////        }
////        start = end + 1;
////        end = start;
////    }
////    if (vprice.size() == 0) return 0;
////    if (vprice.size() == 1) return vprice[0];
////    if (vprice.size() == 2) return vprice[0] + vprice[1];
////    int flag = 0;
////    int n = 2;
////    while (n--)
////    {
////        for (size_t i = 0; i < vprice.size(); i++)
////        {
////            if (vprice[flag] < vprice[i])
////                flag = i;
////        }
////        ret += vprice[flag];
////        vprice[flag] = MIN;
////    }
////    return ret;
////}
////int main()
////{
////    cout << maxProfit({ 1,2,4,2,5,7,2,4,9,0 }) << endl;
////
////
////  /*  int number = 200;
////    int _max = 0;
////    int cur = 0;
////    for (size_t i= 0; i < 32; ++i)
////    {
////        if (number & (1 << i))
////        {
////            ++cur;
////            _max=std::max(cur, _max);
////        }
////        else
////        {
////            cur = 0;
////        }
////    }
////    cout << _max <<endl;*/
////    return 0;
////}
//
////
////int findLengthOfLCIS(vector<int>& nums) {
////    // int _max=1;
////    // int cur=1;
////
////    // for(int i=1;i<nums.size();++i)
////    // {
////    //     if(nums[i-1]<nums[i])
////    //     {
////    //         cur++;
////    //         _max=max(cur,_max);
////    //     }
////    //     else
////    //     {
////    //         cur=1;
////    //     }
////    // }
////    // return _max;
////    int ans = 1;
////    int cur = 1;
////    for (int i = 1; i < nums.size();)
////    {
////        int j = 0;
////        cur = 1;
////        for ( j= i; j < nums.size(); j++)
////        {
////            if()
////        }
////
////
////    }
////    return ans;
////}
////
////
////int main()
////{
////    vector<int> v{ 1,3,5,4,7 };
////    cout << findLengthOfLCIS(v);
////
////
////}
//////
//////
//////
//////struct Node
//////{
//////
//////	Node(int a)
//////		:_a(a)
//////	{
//////		cout << "A()" << endl;
//////	}
//////	~Node()
//////	{
//////		cout << "~A()" << endl;
//////	}
//////	int _a;
//////	weak_ptr<Node> next;
//////	weak_ptr<Node> prev;
//////};
//////
//////void func()
//////{
//////	shared_ptr<Node>n1(new Node(1));
//////	shared_ptr<Node>n2(new Node(2));
//////	n1->next = n2;
//////	cout << "n1:" << n1.use_count() << endl;;
//////	cout << "n2:" << n2.use_count() << endl;;
//////	n2->prev = n1;
//////	cout << "n1:" << n1.use_count() << endl;;
//////	cout << "n2:" << n2.use_count() << endl;;
//////
//////}
//////
//////int main()
//////{
//////	func();
//////	return 0;
//////}
////
////
//////class A
//////{
//////public:
//////	A()
//////	{
//////		cout << "A()" <<endl;
//////	}
//////
//////	~A()
//////	{
//////		cout << "~A()" << endl;
//////	}
//////	static int a;
//////};
//////int A::a=0;
//////
//////void func(int*ptra, int* ptrb)
//////{
//////
//////}
//////
//////class Myclass
//////{
//////public:
//////	static Myclass&get()
//////	{
//////	}
//////	~Myclass()
//////	{
//////		cout << 1;
//////	}
//////	Myclass(const Myclass& M)
//////	{
//////		cout << 2;
//////	}
//////
//////	Myclass& operator =(const Myclass& x)
//////	{
//////		cout << 3;
//////		return *this;
//////	}
//////private: 
//////	Myclass()
//////	{
//////		cout << 4;
//////	}
//////};
//////
//////int main()
//////{
//////	Myclass&obj1= Myclass::get();
//////	return 0;
//////}
//////
//////
//////class UnusualAdd {
//////public:
//////	static int addAB(int A, int B) {
//////		vector<int> VBit(32, 0);
//////		for (size_t i = 0; i < 32; ++i)
//////		{
//////			if ((1 << i) & A)
//////			{
//////				++VBit[i];
//////			}
//////		}
//////		int x0 = 0;
//////		for (size_t i = 0; i < 32; ++i)
//////		{
//////			if ((1 << i) & B)
//////			{
//////				if (VBit[i] == 1)
//////				{
//////					size_t j = i;
//////					while (j<32&&VBit[j] == 1)
//////					{
//////						VBit[j] = 0;
//////						++j;
//////					}
//////					if (j >= 32)
//////						return 0;
//////					VBit[j] = 1;
//////				}
//////				else
//////				{
//////					++VBit[i];
//////				}
//////			}
//////		}
//////		int sum = 0;
//////		for (size_t i = 0; i < 32; ++i)
//////		{
//////			if (VBit[i])
//////			{
//////				sum |= 1 << i;
//////			}
//////		}
//////		return sum;
//////	}
//////};
//////
//////
//////int main()
//////{
//////	cout << UnusualAdd::addAB(1, 3)<<endl;
//////
//////
//////	return 0;
//////}