class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result;
        int a = 0, b = 0;
        for(int i = 0; i < nums.size(); i++)
        {
            a = nums[i];
            b = target - a;
            for(int j = i+1 ; j < nums.size() ; j++ )
            {
                if(nums[j] == b)
                {
                    result.push_back(i);
                    result.push_back(j);
                    return result;
                }
            }
            
        }
        return result;
    }
};

class Solution {
public:
    string toLowerCase(string str) {
        for(int i = 0; i < str.size(); i++)
        {
            if(str[i]<=90 && str[i]>=65)
            {
                str[i] += 32;
            }
        }
        return str;
    }
};

class Solution {
public:
    int minimumEffortPath(vector<vector<int>>& heights) {
        int row_size = heights.size(), col_size = heights[0].size();
        
        //bitset<(row_size-1)*(col_size-1)> map;
        vector<vector<int>> count(row_size,vector<int>(col_size,INT_MAX-1));
        count[0][0] = 0;
        queue<vector<int>> q;
        vector<int> cur     = {0,0};
        vector<int> temp    = {0,0};
        q.push(cur);
        int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
        int step_gap = 0;
        while(!q.empty())
        {
            cur = q.front();
            q.pop();
            for(int i = 0; i<4; i++)
            {
                int x = cur[0]+dx[i],y = cur[1]+dy[i];
                if(x>=0 && x<row_size&&y>=0&&y<col_size)
                {
                    step_gap = abs(heights[cur[0]][cur[1]]-heights[x][y]);
                    step_gap = (step_gap>count[cur[0]][cur[1]])?step_gap:count[cur[0]][cur[1]];
                
                
                if(step_gap >= count[x][y]) continue;
                
                count[x][y] = step_gap;
                temp[0] =x;
                temp[1] = y;
                q.push(temp);
                }
            }
           
        }
        return count[row_size-1][col_size-1];
    }
};

class Solution {
public:
    vector<string> readBinaryWatch(int num) {
        vector<string> res;
        int hours = 0, minutes = 0;
        string tmp ;
        for(hours = 0; hours<12; hours++)
            for( minutes = 0; minutes <60; minutes++)
            {
                if(count(hours) + count(minutes) == num)
                {
                    tmp = to_string(hours);
                    tmp +=":";
                    if (minutes<10)
                        tmp+="0";
                    tmp += to_string(minutes);
                    res.push_back(tmp);
                }
            }
        return res;
    }
    int count(int num)
    {
        int res = 0;
        while(num!=0)
        {
            if(num%2==1)
                res ++;
            num = num>>1;
        }
        return res;
    }
};

class Solution {
public:
    int reverse(int x) {
        unsigned long long result = 0;
        bool flag = 0;
        if(-2147483648>x&&x>2147483647)
            return 0;
        if(x<0)
            flag = 1;
        x = abs(x);

        while(x>0)
        {
            result *=10;
            result += x%10;
            x/=10;
            
            if(result>2147483647)
            return 0;
        }
        //result /=10;
        
        if(flag)
            result *=-1;
        
        return result;
    }
    
};

class Solution {
public:
    int numIdenticalPairs(vector<int>& nums) {
        map<int,int> m;
        auto it=m.begin();
        int count=0;
        for(int i = 0;i<nums.size();i++)
        {
            it = m.find(nums[i]);
            if(it == m.end())
            {
                //cout<<'+'<<endl;
                m.emplace(nums[i],1);
            }
            else
            {
                
                it->second++;
                //cout<<it->first<<'-'<<it->second<<endl;
            }
        }
        for (auto i = m.begin(); i != m.end(); ++i) {
            //cout<<it->first<<' '<<it->second<<endl;
            count += calc_c(i->second);
        }
        return count;
    }
    int calc_c(int num)
    {
        if(num<2)
            return 0;
        return num *(num-1)/2;
    }
};

class Solution {
public:
    int calPoints(vector<string>& ops) {
        stack<int> s;
        int tmp1 = 0,tmp2 = 0;
        for(int i = 0; i< ops.size(); i++)
        {
            //cout<<ops[i]<<'`'<<endl;
            if(ops[i]=="C")
            {
                s.pop();
            }
            else if(ops[i] == "D")
            {
                tmp1 =s.top();

                tmp1*=2;
                //cout<<tmp1<<endl;
                s.push(tmp1);
            }
            else if(ops[i] == "+")
            {
                tmp1 = s.top();
                s.pop();
                tmp2 = s.top();
                s.push(tmp1);
                s.push(tmp1+tmp2);

            }
            else
                s.push(atoi(ops[i].c_str()));
        }
        tmp1 = 0;
        while(!s.empty())
        {
            tmp1 +=s.top();
            s.pop();
        }
        return tmp1;
    }
};

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        map<int,int> m;
        for(int i = 0; i<nums.size();i++)
        {
            if(m.count(nums[i])==0)//insert
                m.insert({nums[i],i});
            else
            {
                if(abs(m[nums[i]] - i)<=k)
                    return true;
                else
                    m[nums[i]] = i;
            }
        }
        return false;
    }
};

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int head= 0,tail = arr.size() - 1,mid = (head+tail)/2;
        while(!(arr[mid]>arr[mid+1]&&arr[mid]>arr[mid-1]))
        {
            if(arr[mid]<arr[mid+1])
            {
                head = mid;
            }
            else
                tail = mid;
            mid = (head+tail)/2;
        }
        return mid;
    }
};

class Solution {
public:
    double average(vector<int>& salary) {
        double min = 1000000,max = 1000,sum = 0;
        for(int i = 0; i< salary.size(); i++)
        {
            sum += salary[i];
            if(salary[i]>max)
                max = salary[i];
            if(salary[i]<min)
                min = salary[i];
        }
        sum -= min;
        sum -= max;
        return sum/(salary.size() - 2);
    }
};

class Solution {
public:
    bool checkValidString(string s) {
        int lcount = 0,scount = 0,count = 0;
        stack<char> s1;
        for(int i = 0 ; i< s.size(); i++)
        {
            if(s[i] == '(')
            {
                lcount ++;
                s1.push('(');
            }
            else if(s[i] == '*')
            {
                scount ++;
                s1.push('*');
            }
            else// encounter )
            {
                if(s1.empty())
                    return false;
                if(lcount == 0)// only * left
                {
                    s1.pop();
                    scount --;
                }
                else if(scount == 0)//only ( left
                {
                    s1.pop();
                    lcount -- ;
                }
                else//now there are * and ( in the stack
                {
                    //first use (
                    while(s1.top()!='(')
                    {
                        s1.pop();
                        count ++;
                    }
                    s1.pop();
                    lcount--;
                    //push back *
                    while(count!=0)
                    {
                        s1.push('*');
                        count -- ;
                    }
                }
            }
        }
        if(lcount > scount)
            return false;
        count = 0;
        while(!s1.empty())
        {
            if(s1.top()=='*')
                count ++;
            else
            {
                count--;
                if(count<0)
                    return false;
            }
            s1.pop();
        }
        return true;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        stack<int> s;
        ListNode * cur = head;
        while(cur)
        {
            s.push(cur->val);
            cur = cur->next;
        }
        cur = head;
        while(cur)
        {
            cur->val = s.top();
            s.pop();
            cur = cur->next;
        }
        return head;
    }
};

class Solution {
public:
    string breakPalindrome(string palindrome) {
        int n = palindrome.size();
        if(n == 1)
            return "";
        for(int i = 0; i<(n/2);i++)
        {
            if(palindrome[i] != 'a')
            {
                palindrome[i] = 'a';
                return palindrome;
            }   
        }
        palindrome[n-1] = 'b';


        return palindrome;
    }
};

class Solution {
public:
    vector<double> cutSquares(vector<int>& square1, vector<int>& square2) {
        double  x1 = square1[0]+square1[2]/2.0,
                y1 = square1[1]+square1[2]/2.0,
                x2 = square2[0]+square2[2]/2.0,
                y2 = square2[1]+square2[2]/2.0;
        vector<double>result(4);
        if(x1==x2)//k infinite
        {
            //rerturn low coord + high coord
            result[0] = x1;
            result[1] = min(square1[1],square2[1]);
            result[2] = x2;
            result[3] = max(square1[1]+square1[2],square2[1]+square2[2]);
        }
        else// there is k, and must calculate two coord
        {
            ///calc k and b
            double k = (y1-y2)/(x1-x2);
            double b = y1 - k*x1;
            // two coord

            if(abs(k) < 1)
            {
                result[0] = min(square1[0],square2[0]);
                result[1] = k*result[0] + b;
                result[2] = max(square1[0]+square1[2],square2[0]+square2[2]);
                result[3] = k*result[2] + b;
            }
            else
            {
                result[1] = min(square1[1],square2[1]);
                result[0] = (result[1] - b)/k;
                result[3] = max(square1[1]+square1[2],square2[1]+square2[2]);
                result[2] = (result[3] - b)/k;
                if(result[0]>=result[2])
                {
                    double tmp = result[1];
                    result[1] = result[3];
                    result[3] = tmp;
                    tmp = result[0];
                    result[0] = result[2];
                    result[2] = tmp; 
                }
            }
        }
        return result;
    }
};

      0 
     / \ 
   -3   9 
   /   / 
 -10  5  ### 解答 这道题主要需要注意边界情况，0，1，2长度的情况 ``` /**  * Definition for a binary tree node.  * struct TreeNode {  *     int val;  *     TreeNode *left;  *     TreeNode *right;  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}  * };  */ class Solution { public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
    if(nums.size()==0)
        return NULL;

    return generate(nums,0,nums.size()-1);
}
TreeNode* generate(vector<int>& nums,int start,int end)
{

    int mid = (start+end)/2;
    TreeNode * tmp = new TreeNode;
    
    if(start==end)//one left
    {
        tmp->val = nums[start];
        return tmp;
    }
        
    if(end - start == 1)// two left
    {
        tmp->val = nums[start];
        TreeNode * tmp2 = new TreeNode;
        tmp2->val = nums[end];
        tmp->right = tmp2;
        return tmp;
    }
    tmp->val = nums[mid];
    tmp->left = generate(nums,start,mid-1);
    tmp->right = generate(nums,mid+1,end);
    return tmp;
} }; ``` ## 第二十题 ### 题目描述 1186. 删除一次得到子数组最大和 难度 中等

class Solution {
public:
    int maximumSum(vector<int>& arr) {
       const int n = arr.size();
       int dp[n][2];
       dp[0][0] = arr[0];
       dp[0][1] = 0;
       int result = arr[0];
       for(int i = 1; i < n ; i ++)
       {
           dp[i][0] = max(0,dp[i-1][0]) + arr[i];
           dp[i][1] = max(dp[i-1][0],arr[i] + dp[i-1][1]);
           result = max(max(result,dp[i][0]),dp[i][1]);
       }
       return result;
    }
};

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size(),max = 1;
        vector<vector<int>> dp (n,vector<int>(n,0));
        // row start, col end, val means is a palindrome or not
        dp[0][0] = 1;
        string result = "";
        int j;
        for(int l = 0; l<n ; l++)// len of palindrome
        {
            for(int i = 0; i+l<n; i++)
            {
                j = i+l;
                if(l==0)
                {
                    dp[i][j] = 1;
                }
                else if(l==1)
                {
                    if(s[i] == s[j])
                        dp[i][j] = 1;
                }
                else
                {
                    if(dp[i+1][j-1]&&s[i]==s[j])
                        dp[i][j] = 1;
                }
                if(dp[i][j]&& l+1 > result.size())
                    result = s.substr(i,l+1);
            }
        }
        return result;
    }
};

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        if(m==0&&n==0)
            return true;
        if(m == 0)
        {
            int i = n-1;
            while(i>=0)
            {
                if(p[i] == '*')
                    i-=2;
                else    
                    return false;
            }
            return true;
        }
        if(n==0)
            return false;
        vector< vector<int> > dp(m + 1,vector<int> (n + 1,0));
        
        dp[0][0] = 1;
        //s[i-1] p[j-1]
        for(int i = 1; i<m+1; i++)
        {
            for(int j = 1; j< n+1; j++)
            {
                if(p[j-1] == '.')
                {
                    if(j>1&& p[j-2] == '*')
                    {
                        dp[i][j] = dp[i-1][j-1] || dp[i][j-2] || dp[i-1][j-3];
                    }
                    else
                        dp[i][j] = dp[i-1][j-1];
                }
                else if(p[j-1] == '*')
                {
                    if(p[j-2] == '.' || p[j-2] == s[i-1])
                        dp[i][j] = (dp[i-1][j-1] || dp[i][j-1] || dp[i-1][j] || dp[i][j-2]);
                    else 
                        if(j>1)
                            dp[i][j] = dp[i][j-2];
                }
                else // alphabet
                {
                    if(s[i-1] == p[j-1])//same as '.'
                        if(dp[i-1][j-1])
                            dp[i][j] = dp[i-1][j-1];
                        else
                        {
                            if(j>2&&p[j-2] == '*' )
                                dp[i][j] = dp[i-1][j-3];
                        }

                }
            }
        }
        for(int i = 1; i<m+1; i++)
        {
            for(int j = 1; j< n+1; j++)
                cout<<dp[i][j]<<' ';
            cout<<endl;
        }

        return dp[m][n];
        
    }
};

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        if(m==0&&n==0)
            return true;
        if(m == 0)
        {
            int i = n-1;
            while(i>=0)
            {
                if(p[i] == '*')
                    i-=2;
                else    
                    return false;
            }
            return true;
        }
        if(n==0)
            return false;
        vector< vector<int> > dp(m + 1,vector<int> (n + 1,0));
        
        dp[0][0] = 1;
        //s[i-1] p[j-1]
        for (int j = 1; j < n+1; j++) 
        {
            if (p[j - 1] == '*') dp[0][j] = dp[0][j - 2];
        }


        for (int i = 1; i < m + 1; i++) 
        {
            for (int j = 1; j < n + 1; j++) 
            {
                if (s[i - 1] == p[j - 1] || p[j - 1] == '.') 
                {
                    dp[i][j] = dp[i - 1][j - 1];
                } 
                else if (p[j - 1] == '*') 
                {
                    if (s[i - 1] == p[j - 2] || p[j - 2] == '.') 
                    {
                        dp[i][j] = dp[i][j - 2] || dp[i - 1][j - 2] || dp[i - 1][j];
                    } 
                    else 
                    {
                       dp[i][j] = dp[i][j - 2];
                    }
                }
            }
        }

        for(int i = 1; i<m+1; i++)
        {
            for(int j = 1; j< n+1; j++)
                cout<<dp[i][j]<<' ';
            cout<<endl;
        }

        return dp[m][n];
        
    }
};

class Solution {
public:
    int totalMoney(int n) {
        int week = n/7;
        int day = n%7;
        int result = 0;
        int carry = 3;
        for(int i = 0 ; i<week; i++)
        {
            carry++;
            result += carry*7;
        }
        if(day)
        {
            carry -=2;
            for(int i = 0;i<day;i++)
            {
                result+=carry;
                carry++;
            }

        }
        return result;
    }
};

class Solution {
public:
    int maximumGap(vector<int>& nums) {
        int n = nums.size();
        int gap = 0;//record tmp gap
        int global_max = -1,local_max = 0;
        int cur_end = 0;
        vector<int> record (5,0);
        if(n<2)
            return 0;
        if(n==2)
            return abs(nums[1]-nums[0]);
        // sort means nlogn
        // so no need to sort completely
        // how about we just focus on those max gap pairs?
        // record cur max gap pair's set, add next element to this set
        // then consider change the max or not
        
        //record[0] start of sorted array
        //record[1] start of max gap
        //record[2] end of max gap
        //record[3] end of sorted array
        //record[4] max len
        while(global_max < local_max)
        {
            global_max = local_max;
            if(nums[0]>=cur_end)
                nums[0] -= (local_max);
            if(nums[1]>=cur_end)
                nums[1] -= (local_max);
            if(nums[0]<nums[1])
            {
                record[0] = nums[0];
                record[1] = nums[0];
                record[2] = nums[1];
                record[3] = nums[1];
                record[4] = nums[1]-nums[0];
            }
            else
            {
                record[0] = nums[1];
                record[1] = nums[1];
                record[2] = nums[0];
                record[3] = nums[0];
                record[4] = nums[0]-nums[1];
            }
            for(int i=2;i<n;i++)
            {
                if(nums[i]>=cur_end)
                    nums[i]-=(local_max);
                if(nums[i]<record[0])
                {
                //in the front of the array
                    gap = record[0] - nums[i];
                    record[0]=nums[i];
                    if(gap > record[4])
                    {
                        record[4] = gap;
                        record[2] = nums[i] + gap;
                        record[1] = nums[i];
                    }
                }
                else if(nums[i]>record[3])//end of the array
                {
                    gap = nums[i] - record[3];
                    record[3] = nums[i];
                    if(gap > record[4])
                    {
                        record[4] = gap;
                        record[1] = nums[i] - gap;
                        record[2] = nums[i];
                    }
                }
                else if(record[1]<nums[i]&&nums[i]<record[2])
                {
                    //in the middle of the max gap
                    // now max gap shrinked
                    // how we get current max gap?
                // we need to compare current gap with sencond\third\4th largest gap
                //in that case, why dont we just sort the array?
                // so we need to record every gap that larger than max/2
                //map maybe worked
                // no it wont work
                    gap = nums[i] - record[1];
                    if(gap >= record[4] - gap)
                    {
                        record[4] = gap;
                        record[2] = nums[i];
                    }
                    else
                    {
                        record[4] = record[4] - gap;
                        record[1] = nums[i];
                    }
                }
            }
            local_max = record[4];
            cur_end = record[2];
            cout<<"local: "<<local_max<<'-';
            cout<<"global: "<<global_max<<endl;
            cout<<"end: "<<cur_end<<endl;
        }
            return global_max;

    }
};

class Solution {
public:
    int maximumGap(vector<int>& nums) {
        int n = nums.size();
        if(n<2)
            return 0;
        if(n==2)
            return abs(nums[1]-nums[0]);
        int max_ = 0,min_ = INT_MAX;
        
        int index = 0;
        for(int i = 0; i< n ; i++)
        {
            if(nums[i]>max_)
                max_ = nums[i];
            if(nums[i]<min_)
                min_ = nums[i];
        }
        int gap = max((max_-min_)/(n-1),1);
        vector< vector<int>> bucket((max_-min_)/gap+1);
        for(int i = 0;i<n;i++)
        {
            index = (nums[i] - min_)/gap;
            bucket[index].push_back(nums[i]);
        }
        int max_gap = 0,prev_max = INT_MAX;
        for(int i =0;i<bucket.size();i++)
        {
            if(bucket[i].size()&& prev_max!=INT_MAX)
            {
                max_gap = max(max_gap,*min_element(bucket[i].begin(),bucket[i].end())-prev_max);
            }
            if(bucket[i].size())
            {
                prev_max = *max_element(bucket[i].begin(),bucket[i].end());
            }
        }
        return max_gap;

    }
};

class Solution {
public:
    int maxDistToClosest(vector<int>& seats) {
        //find first occupied seat
        int cur_max = 0, n = seats.size();
        int cur_gap = 0,prev = 0;
        for(cur_max = 0; cur_max<n && seats[cur_max] == 0; cur_max++);
        prev = cur_max;
        for(int i = cur_max + 1;i<n;i++)
        {
            if(seats[i] == 1)
            {
                cur_gap = (i-prev)/2;
                if(cur_gap>cur_max)
                    cur_max = cur_gap;
                cur_gap = 0;
                prev = i;
            }
            else
            {    
                cur_gap ++;
            }
        }
        if(cur_gap>cur_max)
            cur_max = cur_gap;
        return cur_max;
    }
};

class Solution {
public:
    int integerBreak(int n) {
        int max_ = n-1;
        int times = 0, carry = 0, tmp = 1;
        for(int i = 2; i<=n/2;i++)
        {
            times = n/i;
            carry = n%i;
            if(carry)   
                for(int j = 0;j<i-carry;j++)
                {
                    tmp*=times;
                }
            else
                for(int j = 0;j<i;j++)
                {
                    tmp*=times;
                }

            for(int j = 0;j<carry;j++)
                tmp*=(times+1);

            if(tmp > max_)
                max_ = tmp;
            tmp = 1;
        }
        return max_;
    }
};

class Solution {
public:
    vector<int> peopleIndexes(vector<vector<string>>& favoriteCompanies) {
        vector< set<string> > record(favoriteCompanies.size());
        for(int i =0;i<favoriteCompanies.size();i++)
        {
            for(int j = 0; j< favoriteCompanies[i].size();j++)
            {
                record[i].insert(favoriteCompanies[i][j]);
            }
        }
        bool global_flag = false,local_flag = false;
        int count = 0;
        vector<int> result;
        for(int i =0;i<favoriteCompanies.size();i++)
        {
            count=0;
            for(int k = 0; k<record.size(); k++)//check
            {
                local_flag = false;
                if(k!=i)
                    for(int j = 0; j< favoriteCompanies[i].size();j++)
                    {
                        if(record[k].count(favoriteCompanies[i][j]) == 0 )//dont have
                        {
                            local_flag = true;
                            break;
                        }
                    }
                if(local_flag)
                {
                    count++;
                }
            }
            if(count == favoriteCompanies.size() - 1)
            {
                result.push_back(i);
                count = 0;
            }
        }
        return result;
    }
};

class Solution {
public:
    int numEquivDominoPairs(vector<vector<int>>& dominoes) {
        map<vector<int>,int> m;
        int m1 = 0, n = 0;
        int sum = 0;
        for(int i = 0; i< dominoes.size() ; i++)
        {
            if(m.count(dominoes[i]))//has
                m[dominoes[i]] ++;
            else
                m[dominoes[i]] = 1;
        }
        for (auto i = m.begin(); i != m.end(); ++i)
        {
            m1 = i->first[0];
            n = i->first[1];
            
            if(m.count({n,m1})&&n!=m1)//has
            {
                sum+=(m[{n,m1}] * m[{m1,n}]);
                cout<<n<<' '<<m1<<endl;
            }
            if(i->second > 1)
                sum +=(i->second * (i->second - 1))/2;
            i->second = 0;
        }
        cout<<m[{2,1}]<<endl;
        return sum;
    }
};

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string result = "";
        if(strs.size() == 0)
            return "";
        int min_len = 201;
        for(int i = 0; i<strs.size(); i++)
        {
            if(strs[i].size() < min_len)
                min_len = strs[i].size();
        }
        if(min_len == 0)
            return "";
        char tmp; 
        for(int j = 0; j<min_len;j++)
        {
            tmp = strs[0][j];
            for(int i = 0; i <strs.size();i++)
            {
                if(strs[i][j]!=tmp)
                    return result;
            }
            result.push_back(tmp);
        }
        return result;
        
    }
};

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size();
        //vector< vector<int> > dp(n,vector<int>(n,0));
        vector<int> dp(n,0);
        int cur_index;
        int result = 0;
        for(int i = 0 ; i < n ; i++ )
        {
            if(s[i]=='('&& i!=n-1)//forward
            {
                if(i + 1 < n&&s[i  + 1] == ')')
                {
                    //need to calc consecutive pair
                    //backward find
                    dp[i] = 2;
                    dp[i +1] =2;
                    if(i>0)
                    {
                        dp[i] += dp[i-1];
                        dp[i+1] = dp[i];
                    }
                    
                }
            }
            if(s[i] == ')'&& i>=1)//backward
            {
                if(s[i-1] == ')')//find consecutive pair
                {
                    cur_index = i-1;
                    while(cur_index>0 && s[cur_index] == ')')
                    {
                        if(dp[cur_index] == 0)
                            break;
                        cur_index -= dp[cur_index];
                    }
                        
                    if(cur_index>=0 && s[cur_index] == '(')//match
                    {
                        dp[i] = (i - cur_index + 1);
                        dp[cur_index] = dp[i];
                        if(cur_index >=1)
                        {
                            dp[i] += dp[cur_index - 1];
                            dp[cur_index] = dp[i];
                        }
                    }
                }
            }
            if(dp[i] > result)
                result = dp[i];
        }
 
            
        return result;
    }
};

class Solution {
public:
    int trap(vector<int>& height) {
        if(height.size() <= 2)
            return 0;

        int cur_min = height[0];
        int start = 0,end = 0;
        int sum = 0,cur_sum = 0;
        for(int i = 1; i < height.size() ; i++)//forward
        {
            if(height[i]>=cur_min)
            {
                sum += (i-start-1)*cur_min;
                sum -= cur_sum;
                cur_sum = 0;
                start = i;
                cur_min = height[i];
            }
            else if(height[i] < cur_min)
            {
                cur_sum +=height[i];
            }
        }
        end = start;
        cur_min = height[height.size() - 1];
        start = height.size() -1;
        cur_sum = 0;
        for(int i = height.size() - 2; i >= end; i--)//backward
        {
            if(height[i] >=cur_min)
            {
                sum += abs(start - i -1) * cur_min;
                sum -= cur_sum;
                start = i;
                cur_min = height[i];
                cur_sum = 0;
                //cout<<cur_min<<' '<<start<<' '<<cur_sum<<' '<<sum<<endl;
            }
            else
            {
                cur_sum += height[i];
            }
        }
        return sum;
    }
};

class Solution {
public:
	int trap(vector<int>& height) {
		int n = height.size();
		// left[i]表示i左边的最大值，right[i]表示i右边的最大值
		vector<int> left(n), right(n);
		for (int i = 1; i < n; i++) {
			left[i] = max(left[i - 1], height[i - 1]);
		}
		for (int i = n - 2; i >= 0; i--) {
			right[i] = max(right[i + 1], height[i + 1]);
		}
		int water = 0;
		for (int i = 0; i < n; i++) {
			int level = min(left[i], right[i]);
			water += max(0, level - height[i]);
		}
		return water;
	}
};

class Solution {
    int get(int x) {
        int res=0;
        for (; x; x /= 10) {
            res += x % 10;
        }
        return res;
    }
public:
    int movingCount(int m, int n, int k) {
        if (!k) return 1;
        queue<pair<int,int> > Q;
        int dx[2] = {0, 1};
        int dy[2] = {1, 0};
        vector<vector<int> > vis(m, vector<int>(n, 0));
        Q.push(make_pair(0, 0));
        vis[0][0] = 1;
        int ans = 1;
        while (!Q.empty()) {
            auto [x, y] = Q.front();
            Q.pop();
            for (int i = 0; i < 2; ++i) {
                int tx = dx[i] + x;
                int ty = dy[i] + y;
                if (tx < 0 || tx >= m || ty < 0 || ty >= n || vis[tx][ty] || get(tx) + get(ty) > k) continue;
                Q.push(make_pair(tx, ty));
                vis[tx][ty] = 1;
                ans++;
            }
        }
        return ans;
    }
};

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        int count5 = 0;
        int count10 = 0;
        //sort(bills.begin(),bills.end());
        for(int i = 0; i<bills.size(); i++)
        {
            if(bills[i] == 5)
                count5++;
            else if(bills[i] == 10)
            {
                if(count5 == 0)
                    return false;
                else
                {
                    count5--;
                    count10++;
                }
            }
            else
            {
                if(count10 == 0)
                {
                    if(count5<3)
                        return false;
                    else
                    {
                        count5-=3;
                    }
                }
                else
                {
                    count10--;
                    if(count5)
                        count5--;
                    else
                        return false;
                }
            }
        }
        return true;
    }
};

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int> count_in_dimension(numCourses,0);
        for(int i = 0; i<prerequisites.size() ; i ++)
            count_in_dimension[prerequisites[i][1]] ++;
        stack<int> s;
        int result = 0, cur = 0;
        for(int i = 0 ; i<numCourses ;i++)
            if(count_in_dimension[i] == 0)
                s.push(i);
        while(!s.empty())
        {
            cur = s.top();
            s.pop();
            result++;
            for(int i = 0; i < prerequisites.size(); i++)
            {
                if(prerequisites[i][0] == cur)
                {
                    if(--count_in_dimension[prerequisites[i][1]] == 0)
                        s.push(prerequisites[i][1]);
                }
            }
        }
        return result==numCourses;
    }
};

class Solution {
public:
    string findLongestWord(string s, vector<string>& d) {
        int max_len = 0;
        //int d_index = 0;
        int s_index = 0,di_index=0;
        string result = "";
        for(int i = 0 ; i<d.size(); i++)
        {
            if(d[i].size() < max_len)
                continue;
            else
            {
                //double pointer
                s_index = 0;
                di_index = 0;
                while(s_index < s.size()&& di_index<d[i].size())
                {
                    if(s[s_index] == d[i][di_index])
                    {
                        s_index++;
                        di_index++;
                    }
                    else
                    {
                        s_index++;
                    }
                }
                if(di_index == d[i].size())//match
                {
                    if(di_index>max_len)
                    {
                        max_len = di_index;
                        result = d[i];
                    }
                    else if(di_index == max_len)
                    {
                        //compare
                        result = (result > d[i])?d[i]:result;
                    }
                }
            }
        }
        return result;
    }
};

class Solution {
public:
    int numWays(string s) {
        int sum = 0;
        int cur0 = 0;
        int cur1 = 0;
        long long unsigned int result = 1;
        for(int i = 0; i< s.size(); i++)
            if(s[i]=='1')
                sum++;
        if(sum%3)
            return 0;
        if(sum == 0)
            return ((s.size()-1)*(s.size()-2)/2)%1000000007;;
        sum /= 3;
        //cout<<sum<<endl;
        int i;
        for( i =0 ;cur1<sum; i++)
        {
            if(s[i] == '1')
            {
                cur1++;
            }
        }
        
        for(;s[i]=='0';i++)
            cur0++;
        result *=(cur0+1);
        result %=1000000007;
        //cout<<cur0<<' '<<cur1<<' '<<i<<endl;
        cur1 = 0;
        cur0 = 0;
        for(;cur1<sum;i++)
            if(s[i]=='1')
                cur1++;
        for(;s[i]!='1';i++)
            cur0++;
        result *=(cur0+1);
        result %=1000000007;
        return result;

    }
};

class Solution {
public:
    static bool cmp(string s1,string s2)
    {
        return s1.size()<s2.size();
    }
    int longestStrChain(vector<string>& words) {
        sort(words.begin(),words.end(),cmp);
        
        int length = words.size();
        vector<int> dp(length,1);
        //for(int i = 0;i<length;i++)
          //  cout<<words[i].size()<<' ';
        //cout<<endl;
        int result = 1;
        for(int i = 0; i<length;i++)
        {
            for(int j = i+1;j<length&& words[j].size() <= words[i].size()+1 ;j++)
            {
                if(words[i].size() == words[j].size())
                    continue;
                else if(match(words[i],words[j]))
                {
                    dp[j] = max(dp[j],dp[i]+1);
                    if(dp[j]>result)
                        result = dp[j];
                }
            }
        }
       // for(int i = 0;i<length;i++)
         //   cout<<dp[i]<<' ';
        return result;
    }
    bool match(string s1, string s2)
    {
        int i = 0,j = 0;
        int count = 1;
        while(i<s1.size()&& j<s2.size())
        {
            if(s1[i]==s2[j])
            {
                i++;
                j++;
            }
            else
            {
                if(count)
                {
                    count--;
                    j++;
                }
                else
                    return false;
            }
        }
        return true;
    }
};

class Solution {
public:
    int reachableNodes(vector<vector<int>>& edges, int M, int N) {
        vector<int> visit(N,0);
        vector<int> record(edges.size());
        for(int i = 0; i<edges.size();i++)
            record[i] = edges[i][2];
        vector<vector<int>> consumed(N,vector<int>(edges.size(),0));//record every nodes consume
        //i node, j edge
        queue<pair<int,int>> q;
        q.push(make_pair(0,M));
        int result = 0,tmp = 0;
        int cur_node = 0, cur_step = 0,next_node = 0;
        while(!q.empty())
        {
            cur_node = q.front().first;
            cur_step = q.front().second;
            if(!visit[cur_node])
            {
                result++;
                visit[cur_node] = 1;
            }
            
            q.pop();
            if(cur_step == 0)
                continue;
            for(int i = 0;i<edges.size() ; i++)
            {
                //if(visit[edges[i][0]]&&visit[edges[i][1]]&& edges[i][2] == 0)
                    //continue;
                if(edges[i][0] == cur_node)
                    next_node = edges[i][1];
                else if(edges[i][1] == cur_node)
                    next_node = edges[i][0];
                else
                    continue;
                if(cur_step == record[i])
                {
                    result+=edges[i][2];
                    edges[i][2] =0;
                    consumed[cur_node][i] = record[i];
                }
                else if(cur_step < record[i])//bug
                {
                    if(cur_step > consumed[cur_node][i]&& edges[i][2] > 0)
                    {
                        tmp = (cur_step - consumed[cur_node][i]);
                        if(tmp>=edges[i][2])
                        {
                            result += edges[i][2];
                            edges[i][2] = 0;
                        }
                        else
                        {
                            result += tmp;
                            edges[i][2] -= tmp;
                        }
                        consumed[cur_node][i] = cur_step;
                    }
                }
                else if(cur_step > record[i])
                {
                    result += edges[i][2];
                    q.push(make_pair(next_node,cur_step-record[i]-1));
                    edges[i][2] = 0;
                    consumed[cur_node][i] = record[i];
                }
            }
        }
        return result;
    }
};

class Solution {
public:
    int reachableNodes(vector<vector<int>>& edges, int M, int N) {
        vector<vector<pii>> graph(N);
        for (vector<int> edge: edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            graph[u].push_back({v, w});
            graph[v].push_back({u, w});
        }
        //store graph
        map<int, int> dist;
        dist[0] = 0;
        for (int i = 1; i < N; ++i)
            dist[i] = M+1;

        map<pii, int> used;
        int ans = 0;

        priority_queue<pii, vector<pii>, greater<pii>> pq;
        pq.push({0, 0});

        while (!pq.empty()) {
            pii top = pq.top();
            pq.pop();
            int d = top.first, node = top.second;
            if (d > dist[node]) continue;
            dist[node] = d;

            // Each node is only visited once.  We've reached
            // a node in our original graph.
            ans++;

            for (auto pair: graph[node]) {
                // M - d is how much further we can walk from this node;
                // weight is how many new nodes there are on this edge.
                // v is the maximum utilization of this edge.
                int nei = pair.first;
                int weight = pair.second;
                used[{node, nei}] = min(weight, M - d);

                // d2 is the total distance to reach 'nei' (nei***or) node
                // in the original graph.
                int d2 = d + weight + 1;
                if (d2 < min(dist[nei], M+1)) {
                    pq.push({d2, nei});
                    dist[nei] = d2;
                }
            }
        }

        // At the end, each edge (u, v, w) can be used with a maximum
        // of w new nodes: a max of used[u, v] nodes from one side,
        // and used[v, u] nodes from the other.
        for (vector<int> edge: edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            ans += min(w, used[{u, v}] + used[{v, u}]);
        }
        return ans;
    }
};

class Solution {
public:
    int addDigits(int num) {
        int tmp = 0;
        while(num>=10)
        {
            tmp = 0;
            while(num>0)
            {
                tmp += num%10;
                num/=10;
            }
            num = tmp;
        }
        return num;
    }
};

class Solution {
public:
    string findLexSmallestString(string s, int a, int b) {
        queue<string> q;
        set<string> visit;
        string tmp = "";
        string off_tmp = "";
        string add_tmp = "";
        string result = s;
        q.push(s);
        while(!q.empty())
        {   tmp = q.front();
            q.pop();
            off_tmp = offset(tmp,b);
            add_tmp = add(tmp,a);
            if(!visit.count(add_tmp))
            {
                q.push(add_tmp);
                visit.emplace(add_tmp);
            }
            if(!visit.count(off_tmp))
            {
                q.push(off_tmp);
                visit.emplace(off_tmp);
            }
            result = min(result,min(off_tmp,add_tmp));
        }
        return result;
    
    }
    string offset(string s, int num)
    {
        string result = s.substr(s.size() - num,num);
        return result + s.substr(0,s.size()-num);
    }
    string add(string s, int num)
    {
        int tmp = 0;
        for(int i = 0; i<s.size(); i++)
        {
            char tmp_char = s[i];
            if(i%2)
            {
                tmp = tmp_char - '0' + num;
                tmp%=10;
                s[i] = '0' + tmp;
                
            }
        }
        return s;
    }
};

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        // seems like dp
        vector<vector<int>> dp(text1.size(),vector<int>(text2.size(),0));
        //vector<int> record1(text1.size(),0);
        //vector<int> record2(text2.size(),0);
        for(int i = 0 ; i<text1.size(); i++)
        {
            for(int j = 0; j<text2.size(); j++)
            {
                if(text1[i] == text2[j] )
                {
                    if(i == 0 ||j == 0)
                    {
                        dp[i][j] = 1;
                    }
                    //
                    else
                    {
                        dp[i][j] = dp[i-1][j-1] + 1;
                    }
                }
                else
                {
                    if(i == 0 && j == 0)
                    {
                        dp[i][j] = 0;
                    }
                    else if(i == 0 && j!=0)
                    {
                        dp[i][j] = dp[i][j-1];
                    }
                    else if(i!=0 && j == 0)
                    {
                        dp[i][j] = dp[i-1][j];
                    }
                    else
                    {
                        dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
                    }
                }
            }
        }
            
        return dp[text1.size() - 1][text2.size() - 1];
    }
};

class Solution {
public:
    int minCostToMoveChips(vector<int>& position) {
        int odd_count = 0, even_count = 0;
        for(int i = 0; i< position.size(); i++)
        {
            if(position[i]%2)//odd
                odd_count++;
            else
                even_count++;
        } 
        return min(even_count,odd_count);
    }
};

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> result(n,0);
        int start,end,add;
        for(int i = 0; i < bookings.size(); i++)
        {
            start   = bookings[i][0] - 1;
            end     = bookings[i][1] - 1;
            add = bookings[i][2];
            for(int j = start; j<=end;j++)
                result[j] += add;
        }
        return result;
    }
};

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> result(n,0);
        for(int i = 0; i < bookings.size(); i++)
        {
            result[bookings[i][0] - 1] += bookings[i][2];
            if(bookings[i][1] < n)
                result[bookings[i][1] ] -= bookings[i][2];
        }
        for(int i = 1; i<n; i++)
            result[i] += result[i-1];
        return result;
    }
};

class Solution {
public:
    int countPrimes(int n) {
    if(n<=2)
        return 0;
    vector<int> isPrime(n,1);
    isPrime[0] = 0;
    isPrime[1] = 0;

    for(int i = 2;i*i < n;i++)
    {
        if(isPrime[i])// sieve out every i*m
        {
            for(int j = i;j*i<n;j++)
            {
                isPrime[i*j] = 0;
            }
        }
    }
    int result = 0;
    for(int i =2;i<n;i++)
        if(isPrime[i])
            result++;
    return result;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isUnivalTree(TreeNode* root) {
        stack<TreeNode *> s;
        if(root == NULL)
            return true;
        s.push(root);
        int tmp = root->val;
        TreeNode * cur = NULL;
        while(!s.empty())
        {
            cur = s.top();
            s.pop();
            if(cur->val != tmp)
                return false;
            if(cur->right)
                s.push(cur->right);
            if(cur->left)
                s.push(cur->left);
        }
        return true;
    }
};

class Solution {
public:
    vector<string> findLongestSubarray(vector<string>& array) {
        int a_count = 0,n_count = 0;
        map<int,int> record;
        char tmp;
        int max_len = 0;
        int val = 0,start = 0, end = 0;
        record[0] = -1;
        for(int i = 0; i <array.size(); i++)
        {
            tmp = array[i][0];
            if(tmp>='0' && tmp<='9')
                val++;
            else
                val--;

            if(record.count(val) == 0)//no same before
            {
                record[val] = i;
            }
            else// there is a same record before
            {
                // no need to add this to map, because we are backward finding
                if(i-record[val]> max_len)
                {
                    max_len = i-record[val];
                    start = record[val];
                    end = i;
                }
            }

        }
        //cout<<start<<' '<<end<<' '<<max_len <<' '<<endl;
        if(val == 0)
            return array;
        vector<string> result;
        if(max_len == 0)
            return result;;
        for(int i = start+1; i<=end; i++)
            result.push_back(array[i]);
        return result;
        
    }
};

class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        vector<int> record;
        int cur_1 = 0;
        for(int i = 0;i<nums.size();i++)
        {
            if(nums[i] == 1)
                cur_1++;
            else
            {
                record.push_back(cur_1);
                cur_1 = 0;
                //cout<<cur_1<<' ';
            }
        }
        if(cur_1)
        {
            record.push_back(cur_1);
            //cout<<cur_1<<endl;
        }
        if(record.size() == 1)
            return nums.size()-1;
        int result = record[0];
        for(int i = 0; i< record.size()-1;i++) 
        {
            result = max(result,record[i] + record[i+1]);
        } 
        return result;
        
    }
};

class Solution {
public:
    int translateNum(int num) {
        if(num <10)
            return 1;
        if(num < 26)
            return 2;
        if(num%100>25||num%100<10)
        {
            return translateNum(num/10);
        }
        else
        {
            return translateNum(num/10) + translateNum(num/100);
        }
    }
};

class Solution {
public:
    bool checkPartitioning(string s) {
        string table = "#";
        for(int i = 0;i<s.size(); i++)
        {
            table.push_back(s[i]);
            table.push_back('#');
        }
        vector<int> dp(table.size(),0);
        int max_right = 0;
        int center = 0;
        int mirror = 0;
        int left = 0,right = 0;
        for(int i = 0;i<table.size();i++)
        {
            mirror = 2*center - i;
            if(i<max_right)// find dp[mirror]
            {
                dp[i] = min(max_right - i,dp[mirror]);
            }
            //try expand
            left = i-(1+dp[i]);
            right = i+1+dp[i];
            while(left>=0 && right<table.size() && table[left] == table[right])
            {
                dp[i]++;
                left--;
                right++;
            }
            if(i+dp[i] > max_right)
            {
                center = i;
                max_right = i+dp[i];
            }

        }
        //cout<<"sssss"<<endl;
        /*
        for(int i =0;i<table.size();i++)
            cout<<i<<' ';
        cout<< endl;
        for(int i =0;i<table.size();i++)
            cout<<table[i]<<' ';
        cout<<endl;
        for(int i =0;i<table.size();i++)
            cout<<dp[i]<<' ';
        cout<<endl;
        //*/
        int n = table.size();
        int first_end = 0, second_end = 0;
        for(int i = 1;i<n-2;i++)
        {
            if(dp[i] == i)
            {
                first_end = i+dp[i];
                for(int j = first_end + 1;j<n-1;j++)
                {
                    if(j-dp[j] <= first_end)
                    {
                        second_end = j+(j-first_end);
                        int mid = (second_end+n)/2;
                        
                        //cout<<mid<<endl;
                        if(mid<n-1&&mid + dp[mid] >=n-1)
                            return true;
                    }
                }
            }
        }
        
        // now dfs
        /*int cur_step = 0;
        int cur_end = 0;
        int len = table.size();
        stack<vector<int>> dfs;
        vector<int> record(2);
        for(int i = 1; i<len;i++)
        {
            if(dp[i] == i)
            {
                record[0] = i + dp[i];//cur_end
                record[1] = 1;//cur step
                dfs.push(record);
            }
        }
        while(!dfs.empty())
        {
            cur_end    = dfs.top()[0];
            cur_step   = dfs.top()[1];
            dfs.pop();
            if(cur_end == len-1)
            {
                if(cur_step == 3)
                    return true;
                else
                    continue;
            }
            if(cur_step == 3)
                continue;
            for(int i = cur_end + 1; i<len;i++)
            {
                if(dp[i] && i-dp[i] <= cur_end)
                {
                    record[0] = 2*i - cur_end;
                    record[1] = cur_step+1;
                    dfs.push(record);
                }
            }
        }*/
        return false;
    }
};

class Solution {
public:
    int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int X) {
        int result = 0;
        int total = 0;
        for(int i = 0; i<customers.size();i++)
        {
            if(!grumpy[i])
                total += customers[i];
        }     
        int cur_gain = 0;
        for(int i = 0;i<X;i++)
            if(grumpy[i])
                cur_gain+=customers[i];
        //cout<<total<<' '<<cur_gain<<endl;
        result = total+cur_gain;
        for(int window_left = 1;window_left+X-1<customers.size();window_left++)
        {
            //cout<<total<<' '<<cur_gain<<' '<<window_left<<' '<<window_left+X<< endl;
            if(grumpy[window_left-1])
                cur_gain-=customers[window_left-1];
            if(grumpy[window_left+X-1])
                cur_gain+=customers[window_left+X-1];
            result = max(result,cur_gain+total);
        }
        return result;
    }
};

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        map<string,int> record;
        vector<int> result;
        string tmp;
        int l = words[0].size();
        int total_len = l*words.size();
        //int count = 0;
        bool flag = true;

        for(int i = 0;i<words.size();i++)
        {
            if(!record.count(words[i]))
            {
                record[words[i]] = 1;
            }
            else
                record[words[i]] += 1;
        }
        map<string,int> record_copy;
        for(int i =0;i+total_len-1<s.size();i++)
        {
            // init everytime
            record_copy.clear();
            record_copy.insert(record.begin(),record.end());
            flag = true;
            //count = words.size();
            tmp = s.substr(i,total_len);
            for(int j = 0; j < total_len; j+=l)
            {
                if(record_copy.count(tmp.substr(j,l)))//has this str
                {
                    if(record_copy[tmp.substr(j,l)] == 0)//used up
                    {
                        flag = false;
                        break;
                    }
                    else
                    {
                        record_copy[tmp.substr(j,l)]--;
                        //count--;
                    }
                }
                else
                {
                    flag = false;
                    break;
                }
            }
            if(flag)
                result.push_back(i);
        }
        return result;
    }
};

class Solution {
public:
    int maxProductPath(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        bool flag = false;
        //int result = -1;
        vector< vector<vector<long long>> > dp(m,vector<vector<long long>>(n,vector<long long>(2)));
        if(grid[0][0]>0)
            dp[0][0][0] = grid[0][0];
        else if(grid[0][0]<0)
            dp[0][0][1] = grid[0][0];
        else    
        {
            flag = true;
            dp[0][0][0] = 0;
            dp[0][0][1] = 0;
        }
        
        for(int i = 1;i<m;i++)
        {
            if(grid[i][0] == 0)
                flag = true;
            if(grid[i][0] > 0)
            {
                dp[i][0][0] = (dp[i-1][0][0] * grid[i][0]);
                dp[i][0][1] = (dp[i-1][0][1] * grid[i][0]);
            }
            else
            {
                dp[i][0][1] = (dp[i-1][0][0] * grid[i][0]);
                dp[i][0][0] = (dp[i-1][0][1] * grid[i][0]);
            }
                
        }
        for(int j = 1;j<n;j++)
        {
            if(grid[0][j] == 0)
                flag = true;
            if(grid[0][j] > 0)
            {
                dp[0][j][0] = (dp[0][j-1][0] * grid[0][j]);
                dp[0][j][1] = (dp[0][j-1][1] * grid[0][j]);
            }
            else
            {
                dp[0][j][1] = (dp[0][j-1][0] * grid[0][j]);
                dp[0][j][0] = (dp[0][j-1][1] * grid[0][j]);
            }
        }
        for(int i = 1; i < m; i++)
        {
            for(int j = 1; j < n; j++)
            {
                if(grid[i][j] == 0)
                    flag = true;
                if(grid[i][j] > 0)
                {
                    dp[i][j][0] = max((dp[i-1][j][0]*grid[i][j]),(dp[i][j-1][0]*grid[i][j]));
                    dp[i][j][1] = min((dp[i-1][j][1]*grid[i][j]),(dp[i][j-1][1]*grid[i][j]));
                }
                else
                {
                    dp[i][j][0] = max((dp[i-1][j][1]*grid[i][j]),(dp[i][j-1][1]*grid[i][j]));
                    dp[i][j][1] = min((dp[i-1][j][0]*grid[i][j]),(dp[i][j-1][0]*grid[i][j]));
                }
            }
        }
            
        if(dp[m-1][n-1][0])
            return dp[m-1][n-1][0]%1000000007;
        else if(flag)
            return 0;
        else
            return -1;
    }
};

class Solution {
public:
    int maxScoreSightseeingPair(vector<int>& values) {
        int left = values[0], res = INT_MIN;
        for(int i = 1 ; i<values.size(); i++)
        {
            res = max(left + values[i] - i,res);
            left = max(left,values[i] + i);
        }
        return res;
    }
};

class Solution {
public:
    string largestMultipleOfThree(vector<int>& digits) {
        priority_queue <int,vector<int>,less<int> > q1;
        priority_queue <int,vector<int>,less<int> > q2;
        priority_queue <int,vector<int>,less<int> > record;
        for(int i = 0; i < digits.size();i++)
        {
            if(digits[i]%3 == 0)
            {
                record.push(digits[i]);
            }
            else if(digits[i]%3 == 1)
                q1.push(digits[i]);
            else
                q2.push(digits[i]);
        }
        int s1 = q1.size();
        int s2 = q2.size();
        if(q1.size() == q2.size() || (q1.size()%3 == 0 && q2.size()%3 == 0) || (abs(s1 - s2)%3  == 0) )// can full use
        {
            while(!q1.empty())
            {
                record.push(q1.top());
                q1.pop();
            }
            while(!q2.empty())
            {
                record.push(q2.top());
                q2.pop();
            }
        }
        else// some will left, now is to determine which plan can use most nums
        {
            //total is fixed, so just need to calc left
            int plan1 = abs(s1 - s2) %3;//321 left
            int plan2 = abs(s1%3 - s2%3);//123 left
            if(plan1 > plan2)//use 123
            {
                if(!q1.empty() && q1.size() >= 3)
                {
                    while(q1.size() >= 3)
                    {
                        record.push(q1.top());
                        q1.pop();
                        record.push(q1.top());
                        q1.pop();
                        record.push(q1.top());
                        q1.pop();
                    }
                }
                if(!q2.empty() && q2.size() >= 3)
                {
                    while(q2.size() >= 3)
                    {
                        record.push(q2.top());
                        q2.pop();
                        record.push(q2.top());
                        q2.pop();
                        record.push(q2.top());
                        q2.pop();
                    }
                }
                while(!q1.empty() && !q2.empty())
                {
                    record.push(q1.top());
                    record.push(q2.top());
                    q1.pop();
                    q2.pop();
                }
            }
            else//use 321
            {
                while(!q1.empty() && !q2.empty())
                {
                    record.push(q1.top());
                    record.push(q2.top());
                    q1.pop();
                    q2.pop();
                }
                if(!q1.empty() && q1.size() >= 3)
                {
                    while(q1.size() >= 3)
                    {
                        record.push(q1.top());
                        q1.pop();
                        record.push(q1.top());
                        q1.pop();
                        record.push(q1.top());
                        q1.pop();
                    }
                }
                if(!q2.empty() && q2.size() >= 3)
                {
                    while(q2.size() >= 3)
                    {
                        record.push(q2.top());
                        q2.pop();
                        record.push(q2.top());
                        q2.pop();
                        record.push(q2.top());
                        q2.pop();
                    }
                }
            }
        }
        if(!record.empty() && record.top() == 0)
            return "0";
        string result = "";
        while(!record.empty())
        {
            result.push_back('0'+ record.top());
            record.pop();
        }
        return result;
    }
};

#include<bits/stdc++.h>
using namespace std;
int main()
{
    cout<<3<<' '<<2<<' '<<1<<endl;
    return 0;
}

class Solution {
public:
    double myPow(double x, int n) {
        if(n==0) return 1;
        //考虑到负数右移永远是负数，
        if(n==-1) return 1/x;
        if(n&1) return myPow(x*x, n>>1)*x;
        else return myPow(x*x, n>>1);
    }
};

#include<iostream>

using namespace std;

long long quickpower(long long x, long long y, int k){
    long long ans = 1, temp = x;
    while(y){
        if(y & 1) ans = ans * temp % (k - 1);
        temp = temp * temp % (k - 1);
        y >>= 1;
    }
    return ans ? ans : k - 1;
}

int main(){
    int x, y, k;
    while(cin >> x >> y >> k){
        cout << quickpower(x, y, k) << endl;
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int main()
{
    vector<long long> record(21,1);
    for(int i = 2;i<21;i++)
        record[i] = record[i-1] * i;
    int n;
    while(cin>>n)
        cout<<record[n]<<endl;
}

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int x,y;
    int tmpy,tmpx;
    int result = 0;
    while(cin>>x>>y)
    {
        result = 0;
        while(x>0)
        {
            tmpx = x%10;
            tmpy = y;
            while(tmpy>0)
            {
                result += (tmpx*(tmpy%10));
                tmpy/=10;
            }
            x/=10;
        }
        cout<<result<<endl;
    }
}

#include<bits/stdc++.h>
using namespace std;
bool is_leapyear(int year)
{
    return (year%4==0&&year%100!=0) || year%400 == 0;
}
int main()
{
    vector<int> leap{31,29,31,30,31,30,31,31,30,31,30,31};
    vector<int> norm{31,28,31,30,31,30,31,31,30,31,30,31};
    int year,month,day;
    int result = 0;
    while(cin>>year>>month>>day)
    {
        result = 0;
        if(is_leapyear(year))
        {
            for(int i = 0;i < month-1;i++)
            {
                result +=leap[i];
            }
            result += day;
        }
        else
        {
            for(int i = 0;i < month-1;i++)
            {
                result +=norm[i];
            }
            result += day;
        }
        cout<<result<<endl;
    }
}

#include<bits/stdc++.h>
using namespace std;
int judge(int n)
{
    int tmp = 0;
    for(int i = 1;i<=n/2; i++)
    {
        if(n%i == 0)
            tmp += i;
    }
    if(tmp>n)
        return 1;
    else if(tmp == n)
        return 0;
    else
        return -1;
}
int main()
{
    vector<int> com;
    vector<int> big;
    for(int i = 2;i<=60;i++)
    {
        if(judge(i) == 1)
            big.push_back(i);
        else if(judge(i) == 0)
            com.push_back(i);
            
    }
    cout<<"E:";
    for(int i = 0;i<com.size();i++)
        cout<<' '<<com[i];
    cout<<endl;
    cout<<"G:";
    for(int i = 0;i<big.size();i++)
        cout<<' '<<big[i];
    cout<<endl;
}

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long a0,a1,p,q,k;
    cin>>a0>>a1>>p>>q>>k;
    vector<long long> result(k+1);
    result[0] = a0;
    result[1] = a1;
    for(int i =2;i<k+1;i++)
    {
        result[i] = (p*result[i-1] + q*result[i-2])%10000;
    }
    cout<<result[k]%10000<<endl;
}

#include<bits/stdc++.h>
using namespace std;
int main()
{
    //vector<int> record(1000000);
    int n;
    int tmp = 0;
    int max = 0;
    int cur_sum = 0;
    while(cin>>n)
    {
        cin>>tmp;
        max = tmp;
        cur_sum = tmp;
        for(int i =1;i<n;i++)
        {
            cin>>tmp;
            cur_sum += tmp;
            if(cur_sum >max)
            {
                max = cur_sum;
            }
            if(cur_sum < 0)
            {
                cur_sum = 0;
            }
        }
        cout<<max<<endl;
    }
}

#include<bits/stdc++.h>
using namespace std;
int main()
{
    vector<vector<int>> input_set(100,vector<int>(2));
    vector<vector<int>>   processed_set;
    int N,M;
    int front,tail;
    while(cin>>N>>M)
    {
        processed_set.clear();
        for(int i =0;i<M;i++)
            cin>>input_set[i][0]>>input_set[i][1];
        for(int i = 0;i<M;i++)
        {
            int pre = -1;
            bool flag = true;
            front = input_set[i][0];
            tail = input_set[i][1];
            for(int j = 0;j<processed_set.size();j++)
            {
                if( (front >= processed_set[j][0]&& front <=processed_set[j][1]) ||(tail >= processed_set[j][0] && tail <= processed_set[j][1]) || (front <=processed_set[j][0] && tail>= processed_set[j][1]))
                {
                    processed_set[j][0] = min(front,processed_set[j][0]);
                    processed_set[j][1] = max(tail,processed_set[j][1]);
                    front = processed_set[j][0];
                    tail = processed_set[j][1];
                    flag = false;
                    if(pre!= -1)
                    {
                        processed_set[pre][0] = -1;
                        processed_set[pre][1] = -1;
                    }
                    pre = j;
                    
                }
            }
            if(flag)
            {
                processed_set.push_back({front,tail});
            }
        }
        for(int j = 0;j<processed_set.size();j++)
            if(processed_set[j][0] != -1)
            {
                N-=(processed_set[j][1] - processed_set[j][0] + 1);
                //cout<<processed_set[j][0]<<' '<<processed_set[j][1]<<endl;
            }

        cout<<N+1<<endl;
    }
}

#include<bits/stdc++.h>
using namespace std;
string divide_2(string s, bool &flag)
{
    string result = "";
    int tmp = 0;
    for(int i = 0;i<s.size();i++)
    {
        tmp = tmp*10 + s[i] - '0';
        result += tmp/2 + '0';
        tmp = tmp%2;
    }
    if(tmp)
        flag = true;//means odd num
    return result;
}
string multi_2(string s)
{
    string result(s.size()+1,'0');
    int carry = 0;
    int tmp = 0;
    for(int i = s.size()-1 ;i>=0;i--)
    {
        //cout<<result<<endl;
        tmp = (s[i] - '0') *2;
        if(tmp +carry >= 10)
        {
            result[i+1] = (tmp +carry)%10 +'0';
            carry = 1;
        }
        else
        {
            result[i+1] = tmp +carry +'0';
            carry = 0;
        }
    }
    if(carry)
        result[0] = '1';
    else
        if(result.size()>1)
            result = result.substr(1,s.size());
    return result;
}
string convert(string s)
{
    string result = "";
    bool flag = false;
    while(s.size() > 0)
    {
        flag = false;
        s = divide_2(s,flag);
        //cout<<s<<endl;
        if(flag)
            result += '1';
        else
            result += '0';
        int i = 0;
        while(s[i] == '0')
            i++;
        s = s.substr(i,s.size() - i);
    }
    //now result is a binary reverse string, all we need is to transfer this string to decimal
    //cout<<result<<endl;
    string ans = "0";
    for(int i =0;i<result.size();i++)
    {
        ans = multi_2(ans);
        ans[ans.size() -1] += result[i] - '0';
        
        //cout<<ans<<endl;
    }
    return ans;
    
}
int main()
{
    string s;
    cin>>s;
    //cout<<multi_2(s)<<endl;
    cout<<convert(s)<<endl;
}

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int N;
    cin>>N;
    string tmp1;
    string tmp = "";
    string id;
    map<string,string> record;
    for(int i = 0;i<N ; i++)
    {
        cin>>id;
        tmp = id;
        for(int i = 0;i<3;i++)
        {
            cin>>tmp1;
            tmp+=' ';
            tmp += tmp1;
        }
        record[id] = tmp;
    }
    cin>>N;
    for(int i = 0; i<N ; i++)
    {
        cin>>id;
        if(record.count(id))//has
        {
            cout<<record[id]<<endl;
        }
        else
            cout<<"No Answer!"<<endl;
    }
}

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    string s;
    set<string> s_set;
    queue<pair<string,int>>q;
    string tmp;
    int step;
    while(cin>>n)
    {
        bool flag = false;
        cin>>s;
        while(!q.empty())
            q.pop();
        s_set.clear();
        q.push(make_pair(s,0));
        s_set.emplace(s);
        while(!q.empty())
        {
            s = q.front().first;
            step = q.front().second;
            q.pop();
            if(s.find("2012") != s.npos)
            {
                cout<<step<<endl;
                flag = true;
                break;
            }
            else
            {
                for(int i = 0; i<s.size() - 1; i++)
                {
                    tmp = s;
                    tmp[i] = s[i+1];
                    tmp[i+1] = s[i];
                    if(s_set.count(tmp) == 0)
                    {
                        s_set.emplace(tmp);
                        q.push(make_pair(tmp,step+1));
                    }
                }
            }
        }
        if(!flag)
            cout<<-1<<endl;
    }
}

#include<iostream>
#include<string>
using namespace std;
string divide(string origin,int origin_base,int target_base, int & num)
{
    string result = "";
    int n = origin.size();
    int tmp = 0;
    int remain = 0;
    for(int i = 0;i<n;i++)
    {
        //cout<<remain<<endl;
        remain *= origin_base;
        if(origin[i] >='0' && origin[i] <='9')
        {
            remain += origin[i] - '0';
        }
        else
        {
            remain += origin[i] - 'A' + 10;
        }
        tmp = remain/target_base;
        remain = remain%target_base;
        if(tmp>9)
            result +=('A' + tmp - 10);
        else
            result += ('0' + tmp);
    }
    num = remain;
    //cout<<result<<endl;
    return result;
}
string multi(string origin,int origin_base,int target_base)
{
    string result(origin.size()+1,'0');
    int carry = 0;
    int tmp = 0;
    for(int i = origin.size() - 1; i>=0 ; i-- )
    {
        if(origin[i] >='0' && origin[i] <='9')
        {
            tmp = origin[i] - '0';
        }
        else
        {
            tmp = origin[i] - 'A' + 10;
        }
        tmp *= target_base;
        tmp += carry;
        carry = tmp/origin_base;
        tmp %= origin_base;
        if(tmp > 9)
            result[i+1] = (tmp - 10 + 'A');
        else
            result[i+1] = (tmp + '0');
    }
    if(carry)
    {
        if(carry > 9)
            result[0] = (carry + 'A' - 10);
        else
            result[0] = '0' + carry;
        return result;
    }
    else
        return result.substr(1,result.size()-1);
}
int main()
{
    string origin;
    string result = "";
    long long  origin_base;
    long long  target_base;
    cin>>origin_base>>target_base;
    cin>>origin;
    //cout<<origin<<' '<<origin_base<<' '<<target_base<<endl;
    int remain;
    while(origin.size() > 0)
    {
        origin = divide(origin,origin_base,target_base,remain);
        //cout<<origin<<' '<<remain<<endl;
        
        if(remain > 9)
            result += 'a' + remain - 10;
        else
            result += '0' + remain;
        while(origin[0] == '0')
            origin = origin.substr(1,origin.size() - 1);
    }
    for(int i = result.size() - 1; i >= 0 ; i-- )
        cout<<result[i];
    cout<<endl;
    
}

#include<bits/stdc++.h>
using namespace std;
int reverse(int n)
{
    int result = 0;
    result += n/1000;
    n%=1000;
    result += (n/100) *10;
    n%=100;
    result += (n/10) * 100;
    n%=10;
    result += n*1000;
    return result;
}
int main()
{
    for(int i = 1000; i <= 1111 ; i++)
    {
        if(9*i == reverse(i))
            cout<<i<<endl;
    }
}

#include<bits/stdc++.h>
using namespace std;
int reverse(int n)
{
    int result = 0;
    int tmp = 0;
    while(n>0)
    {
        result*=10;
        tmp = n%10;
        result += tmp;
        n/=10;
    }
    return result;
}
bool judge(int n)
{
    int tmp = n*n;
    return tmp == reverse(tmp);
    
}
int main()
{
    for(int i = 0;i<=256;i++)
    {
        if(judge(i))
            cout<<i<<endl;
    }
}

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m;
    cin>>n;
    map<string,bool> proxy_record;
    string tmp;
    for(int i = 0;i<n;i++)
    {
        cin>>tmp;
        proxy_record[tmp] = false;
    }
    cin>>m;
    vector<string> visit_array;
    for(int i = 0; i< m ; i++)
    {
        cin>>tmp;
        visit_array.push_back(tmp);
    }
    int count = 0;
    int result = 0;
    for(int i = 0 ; i < m ; i++)
    {
        tmp = visit_array[i];
        if(proxy_record.count(tmp) && proxy_record[tmp] == false)
        {
            count ++;
            proxy_record[tmp] = true;
            if(count == n)
            {
                count = 1;
                result ++;
                for(auto it = proxy_record.begin() ; it != proxy_record.end() ; it++)
                {
                    if(it->first!=tmp)
                        it->second = false;
                }
            }
        }
        else if(n==1&& proxy_record[tmp] == true)
        {
            result = -1;
            break;
        }
    }

    cout<<result<<endl;
}

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    string result = "AAAA";
    while(cin>>s)
    {
        result[0] = s[3];
        result[1] = s[2];
        result[2] = s[1];
        result[3] = s[0];
        cout<<result<<endl;
    }
}

#include<bits/stdc++.h>
using namespace std;
int main()
{
    vector<int> layout = {1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,6,7,7,7,8,8,8,8};
    vector<int> times =  {1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,4,1,2,3,1,2,3,4};
    string s;
    int pre;
    int cur;
    int result;
    while(cin>>s)
    {
        pre = s[0] - 'a';
        result = times[pre];
        for(int i = 1 ; i<s.size() ; i++)
        {
            cur = s[i] - 'a';
            if(layout[cur] == layout[pre])
                result+=2;
            result += times[cur];
            pre = cur;
        }
        cout<<result<<endl;
    }
}

#include<bits/stdc++.h>
using namespace std;
bool is_prime(int n)
{
    for(int i = 2 ; i*i <= n ; i++)
    {
        if(n%i == 0)
            return false;
    }
    return true;
}
int main()
{
    int n;
    int result = 0;
    while(cin>>n)
    {
        result = 0;
        while(!is_prime(n))
        {
            for(int i = 2;i*i<=n;i++)
            {
                if(n%i==0 )
                {
                    n/=i;
                    break;
                }
            }
            result++;
        }
        result++;
        cout<<result<<endl;
    }
}

f(2m + 1) = f(2m)， f(2m) = f(2m - 1) + f(m)， 初始条件：f(1) = 1。
 
证明:
 
证明的要点是考虑划分中是否有1。
 
记: A(n) = n的所有划分组成的集合， B(n) = n的所有含有1的划分组成的集合， C(n) = n的所有不含1的划分组成的集合， 则有: A(n) = B(n)∪C(n)。
 
又记: f(n) = A(n)中元素的个数， g(n) = B(n)中元素的个数， h(n) = C(n)中元素的个数， 易知: f(n) = g(n) + h(n)。
 
以上记号的具体例子见文末。
 
我们先来证明: f(2m + 1) = f(2m)， 首先，2m + 1 的每个划分中至少有一个1，去掉这个1，就得到 2m 的一个划分，故 f(2m + 1)≤f(2m)。 其次，2m 的每个划分加上个1，就构成了 2m + 1 的一个划分，故 f(2m)≤f(2m + 1)。 综上，f(2m + 1) = f(2m)。
 
接着我们要证明: f(2m) = f(2m - 1) + f(m)， 把 B(2m) 中的划分中的1去掉一个，就得到 A(2m - 1) 中的一个划分，故 g(2m)≤f(2m - 1)。 把 A(2m - 1) 中的划分加上一个1，就得到 B(2m) 中的一个划分，故 f(2m - 1)≤g(2m)。 综上，g(2m) = f(2m - 1)。
 
把 C(2m) 中的划分的元素都除以2，就得到 A(m) 中的一个划分，故 h(2m)≤f(m)。 把 A(m) 中的划分的元素都乘2，就得到 C(2m) 中的一个划分，故 f(m)≤h(2m)。 综上，h(2m) = f(m)。
 
所以: f(2m) = g(2m) + h(2m) = f(2m - 1) + f(m)。                                            
 
这就证明了我们的递推公式。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    vector<long long> dp(1000001,-1);
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 2;
    dp[4] = 3;
    int max_index = 4;
    while(cin>>n)
    {
        if(max_index >=n)
            cout<<dp[n]<<endl;
        else
        {
            for(int i = max_index; i<=n;i++)
            {
                if(i%2)
                    dp[i] = dp[i-1];
                else
                    dp[i] = (dp[i-1] + dp[i/2])%1000000000;
            }
            cout<<dp[n]%1000000000<<endl;
            max_index = n;
        }
    }
}

#include<bits/stdc++.h>
using namespace std;
bool cmp(const vector<int> a,const vector<int> b)
{
    if(a[1] == b[1])
        return a[0]<b[0];
    else
        return a[1]<b[1];
}
int main()
{
    int n;
    cin>>n;
    vector<vector<int>> record(n,vector<int>(2));
    for(int i = 0; i < n ; i++)
    {
        cin>>record[i][0]>>record[i][1];
    }
    sort(record.begin(),record.end(),cmp);
    for(int i = 0; i < n ; i++)
    {
        cout<<record[i][0]<<' '<<record[i][1]<<endl;
    }
}

#include<bits/stdc++.h>
using namespace std;
int main()
{
    double x0,y0,z0;
    double x1,y1,z1;
    cin>>x0>>y0>>z0>>x1>>y1>>z1;
    double radius = sqrt((x0-x1)*(x0-x1) + (y0-y1)*(y0-y1) + (z0-z1)*(z0-z1));
    double V = (4.0/3.0)*acos(-1) * radius*radius*radius;
    cout<<setiosflags(ios::fixed)<<setprecision(3);
    cout<<radius<<' '<<V<<endl;
}

#include<iostream>
#include<cstdio>
 
using namespace std;
 
const int maxn=100;
 
int weight[maxn];
int dp[maxn];
 
//每张邮票价值为1，求背包容量M,N个物品，装满的前提下获得最小的价值；
 
//对于dp[i][j]来说，
//（1）如果放入第i个物品可以填满j容量的背包，那么使用前i-1个物品可以填满j-w[i]容量的背包，于是dp[i][j]=dp[i-1][j-w[i]]+1；
//（2）如果不放入第i个物品也可以填满j容量的背包,意味着只使用前i-1个物品仍然可以填满j容量的背包，dp[i][j]=dp[i-1][j]。
//总结以上两种情况：dp[i][j]取其中较小的。
 
//如果前i个物品不能存满背包，设置dp[i][j]为一个超过总价值的数，当更大的i,j需要使用较小的i,j的dp时，dp都不能存满背包，则较大的dp也不能存满背包。
//边界条件：dp[0][j]=MAX,不存放物品时，任何非零容量都不能存满;dp[i][0]=0，容量为0，总是可以填满且总价值为0；
//状态转移：dp[i][j]=min(dp[i-1][j-w[i]]+1,dp[i-1][j]);任何情况下，dp都不会超过设置的max值。
//优化：可以看到dp[i][j]只和上一行的数据有关，简化成dp[j]=min(dp[j-w[i]]+1,dp[j])，且遍历到dp[j]时，dp[j-w[i]]值应还未修改，所以j从后向前遍历。
int main(){
    int M,N;
    while(cin>>M>>N){
        for(int i=0;i<N;++i){
            scanf("%d",&weight[i]);
        }
        for(int i=0;i<=M;i++){
            dp[i]=maxn;
        }
        dp[0]=0;
        for(int i=0;i<N;i++){
            for(int j=M;j>=weight[i];j--){
                dp[j]=min(dp[j-weight[i]]+1,dp[j]);
            }
        }
        if(dp[M]==maxn){
            cout<<0<<endl;
        }else{
            cout<<dp[M]<<endl;
        }
    }
    return 0;
}

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include<iomanip>
using namespace std;
bool cmp(vector<double> a, vector<double> b)
{
    return (a[0]/a[1]) >(b[0]/b[1]);
}
int main()
{
    int total = 0;
    int n = 0;
    double result = 0;
    vector<vector<double>> record(1000,vector<double>(2));
    while(cin>>total>>n)
    {
        if(total == -1 && n == -1)
            break;
        for(int i = 0;i<n;i++)
        {
            cin>>record[i][0]>>record[i][1];
        }
        sort(record.begin(),record.begin()+n,cmp);
        for(int i = 0; i<n && total >0;i++)
        {
            if(total >= record[i][1])
            {
                result += record[i][0];
                total -= record[i][1];
            }
            else
            {
                result += (total/record[i][1]) * record[i][0];
                break;
            }
        }
        cout<<setiosflags(ios::fixed)<<setprecision(3);
        cout<<result<<endl;

    }
}

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,m;
	//int carry = 1;
	cin>>n>>m;
	vector<int> record(n);
	vector<int> result(10,0);
	
	for(int i = 0;i<n;i++)
		cin>>record[i];
	int max = 0;
	int index = 0;
	for(int i = 0;i<m;i++)
	{
		for(int j = 0; j < 10;j ++)
			result[j] = 0;
		for(int j = 0 ;j<n;j++)
		{
			result[record[j]%10]++;
			record[j]/=10;
		}
		max = 0;
		index = 0;
		for(int i = 0;i<10;i++)
		{
			if(result[i]>max)
			{
				max = result[i];
				index = i;
			}
		}
		cout<<index<<endl;
	}
}

#include<bits/stdc++.h>
using namespace std;
vector<int> a(25);
int dp[25];
int n;
int LIS_nlgn() {  
    int len = 1;  
    dp[1] = a[1];  
  
    for (int i = 2; i <= n; ++i) {  
        if (a[i] <= dp[len]) {  
            dp[++len] = a[i];  
        } else {  
            int pos = lower_bound(dp, dp + len, a[i]) - dp;  
            dp[pos] = a[i];  
        }  
    }  
    return len;  
}  
int main()
{
	cin>>n;
	for(int i = 0; i< n; i++)
	{
		cin>>a[i];
	}
	int result = LIS_nlgn();
	cout<<result-1<<endl;
}

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int total;
	int n;
	while(cin>>total>>n)
	{
		vector<int> dp(total+1,0);
		dp[0] = 1;
		vector<int> record(n);
		for(int i = 0;i<n;i++)
		{
			cin>>record[i];
		}
		//int maxlen = 0;
		for(int i =0; i<n;i++)
		{
			for(int j = total;j>=0;j--)
			{
				if(dp[j])
				{
					if(j+record[i] <= total)
						dp[j+record[i]] = 1;
				}
			}
		}
		if(dp[total])
			cout<<"yes!"<<endl;
		else
			cout<<"no!"<<endl;
	}
}

#include <bits/stdc++.h>  
using namespace std;  
  
const int maxn = 105;  
struct node {  
    int u, v, w;  
}edge[maxn * maxn];  
int cmp(node A, node B) {  
    return A.w < B.w;  
}  
int fa[maxn];  
int find(int x) {  
    if (x == fa[x]) return x;  
    fa[x] = find(fa[x]);  
    return fa[x];  
}  
int main(){  
    int N;
	int flag;
	
    while(cin>>N)
	{  
        if(N==0)
			break;
        for (int i = 0; i < (N*(N-1))/2; i++) 
		{  
            scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w); 
			cin>>flag;
			if(flag)
				edge[i].w = 0;
        }  
        for (int i = 1; i <= N; i++) fa[i] = i;  
        sort(edge, edge + (N*(N-1))/2, cmp);  
        int sum = 0;  
        int total = 0;  
        for (int i = 0; i < (N*(N-1))/2; i++) {  
            int fx = find(edge[i].u);  
            int fy = find(edge[i].v);  
            if (fx != fy) {  
                fa[fx] = fy;  
                sum += edge[i].w;  
                total++;//统计加入边数量  
            }  
        }  
        if (total < N - 1)//不能生成树  
            printf("?\n");  
        else printf("%d\n", sum);  
    }  
    return 0;  
}  

#include<bits/stdc++.h>
using namespace  std;
int matrix[1005][1005];
int patched_matrix[1005][1005];
int row_state[1005] = {0};// have how many none 0 nums
int col_state[1005] = {0};
void process_matrix(int row,int col)
{
    bool flag = true;
    while(flag)//untill cannot change
    {
        flag = false;
        for(int i =0;i<row;i++)
        {
            if(row_state[i] >1 && row_state[i] < row)//means this row can be solved
            {
                flag = true;//marked
                int first = -1;
                int second = -1;
                int first_val = -1;
                int second_val = -1;
                for(int j = 0 ;j < col; j++)
                {
                    if(matrix[i][j] || patched_matrix[i][j])
                    {
                        if(first!=-1)
                        {
                            second = j;
                            second_val = max(matrix[i][j],patched_matrix[i][j]);
                            break;
                        }
                        else
                        {
                            first = j;
                            first_val = max(matrix[i][j],patched_matrix[i][j]);
                        }
                    }
                }
                int carry = (second_val - first_val) / (second - first);
                int start = first_val - first * carry;
                //now fix it
                for(int j = 0 ;j < col; j++)
                {
                    if(matrix[i][j] == 0 && patched_matrix[i][j] == 0)
                    {
                        patched_matrix[i][j] = start;
                        col_state[j] ++;
                    }
                    start += carry;
                }
                row_state[i] = row;

            }
        }
        for(int j=0;j<col;j++)
        {
            if(col_state[j] >1 && col_state[j] < row)//means this col can be solved
            {
                flag = true;//marked
                int first = -1;
                int second = -1;
                int first_val = -1;
                int second_val = -1;
                for(int i= 0 ;i < row; i++)
                {
                    if(matrix[i][j] || patched_matrix[i][j])
                    {
                        if(first!=-1)
                        {
                            second = i;
                            second_val = max(matrix[i][j],patched_matrix[i][j]);
                            break;
                        }
                        else
                        {
                            first = i;
                            first_val = max(matrix[i][j],patched_matrix[i][j]);
                        }
                    }
                }
                int carry = (second_val - first_val) / (second - first);
                int start = first_val - first * carry;
                //now fix it
                for(int i = 0 ;i < row; i++)
                {
                    if(matrix[i][j] == 0 && patched_matrix[i][j] == 0)
                    {
                        patched_matrix[i][j] = start;
                        row_state[i] ++;
                    }
                    start += carry;
                }
                col_state[j] = col;
            }
        }
    }
}
int main()
{
    int row,col;
    scanf("%d%d",&row,&col);
    for(int i =0;i<row;i++)
    {
        for(int j = 0; j < col;j++)
        {
            scanf("%d",&matrix[i][j]);
            if(matrix[i][j])
            {
                row_state[i] ++;
                col_state[j] ++;
            }
        }
    }
    process_matrix(row,col);
    /*for(int i =0 ;i<row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            cout<<patched_matrix[i][j]<<' ';
        }
        cout<<endl;
    }*/
    for(int i =0 ;i<row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            if(patched_matrix[i][j])
            {
                printf("%d %d %d\n",i+1,j+1,patched_matrix[i][j]);

            }

        }
    }


}

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
int g[2005][2005];
int weight[2005];
int result;
int n, m, q;
void dfs(int start, int remain, int cur_sum)
{
    cur_sum += weight[start];
    //cout<<start<<' '<<remain<<' '<<cur_sum<<endl;
    for(int i = 0; i<=n;i++)
    {
        if(remain >= g[start][i])
            dfs(i,remain - g[start][i],cur_sum);
        else
            result = result > cur_sum ? result: cur_sum;
    }
}
int main()
{

    cin>>n>>m>>q;
    for(int i = 1;i<=n;i++)
        cin>>weight[i];
    memset(g,INF,sizeof(g));
    for(int i = 0;i<m;i++)
    {
        int x, y, w;
        cin>>x>>y>>w;
        g[x][y] = w;
    }
    int start, cost;
    for(int i = 0; i<q; i++)
    {
        //cout<<'-'<<endl;
        result = 0;
        cin>>start>>cost;
        dfs(start,cost,0);
        cout<<result<<endl;
    }

}

#define ll long long
#define inf 0x3f3f3f3f
#define MAX 10000007
#define vec vector<int>
#define P pair<int,int>

int main() {
	string s; int n, dp[MAX], sum;
	while (cin >> n >> s) {
		if (n == 0) { cout << 0 << endl; continue; }
		int ma = -1, v; sum = 0;
		memset(dp, 0, sizeof(dp));
		if (s[0] == '0')dp[0] = 1, ma = 1;
		else dp[0] = -1, sum++;
		//翻转0的话：等价于将0看作1，1看作-1的最大连续区间和的问题
		for (int i = 1; i < n; i++) {
			if (s[i] == '1')sum++, v = -1;
			else v = 1;
			if (dp[i - 1] > 0)dp[i] = dp[i - 1] + v;
			else dp[i] = v;
			if (dp[i] > ma)ma = dp[i];
		}
		if (ma >= 0)cout << ma + sum << endl;
		else cout << sum << endl;
	}
}

#include<bits/stdc++.h>
using namespace std;
int dp[101][101] = {0};

int main()
{
    string s1,s2;
    while(cin>>s1>>s2)
    {
        memset(dp,0,sizeof(dp));
        int result = 0, r = 0;
        for(int j = 0 ; j < s2.length(); j++)
        {
            if(s2[j] == s1[0])
            {
                dp[0][j] = 1;
                result = 1;
            }
        }
        for(int i = 0; i<s1.length(); i++)
        {
            if(s1[i] == s2[0])
            {
                dp[i][0] = 1;
                result = 1;
                r = i;
            }
        }

        for(int i = 1; i<s1.length() ; i++)
        {
            for(int j = 1 ; j < s2.length(); j++)
            {
                if(s1[i] == s2[j])
                {

                    dp[i][j] = dp[i-1][j-1] +1;
                    if(dp[i][j] >= result)
                    {
                        result = dp[i][j];
                        r = i;
                    }
                }
            }
        }
        cout<<result<<endl;
        cout<<s1.substr(r-result+1,result)<<endl;
    }
}

#include<bits/stdc++.h>
using namespace std;
int record[205][205];
int row_max_sum[205];
int tmp_sum[205];
int n,m,result;
int main()
{
    while(cin>>n>>m)
    {
        for(int i = 0; i< n; i++)
            for(int j = 0; j< m; j++)
                cin>>record[i][j];
        for(int i = 0; i<n ;i++)
        {
            if(m == 1)
                row_max_sum[i] = record[i][0];
            else if(m == 2)
                row_max_sum[i] = max(record[i][0],record[i][1]);
            else if(m == 3)
                row_max_sum[i] = max(record[i][0] + record[i][2], record[i][1]);
            else
            {

                tmp_sum[0] =record[i][0];
                tmp_sum[1] = record[i][1];
                tmp_sum[2] = record[i][2] + record[i][0];
                int tmp_max = max(tmp_sum[1],tmp_sum[2]);
                for(int j = 3;j<m;j++)
                {
                    tmp_sum[j] = max(tmp_sum[j-2],tmp_sum[j-3]) + record[i][j];
                    tmp_max = max(tmp_sum[j],tmp_max);
                }
                row_max_sum[i] = tmp_max;
            }
        }
        if(n == 1)
            result = row_max_sum[0];
        else if(n == 2)
            result = max(row_max_sum[0],row_max_sum[1]);
        else if(n==3)
            result = max(row_max_sum[0] + row_max_sum[2] , row_max_sum[1]);
        else
        {
            row_max_sum[2] += row_max_sum[0];
            result = max(row_max_sum[2],row_max_sum[1]);
            for(int i = 3; i< n; i++)
            {
                row_max_sum[i] = max(row_max_sum[i-2],row_max_sum[i-3]) + row_max_sum[i];
                result = max(result,row_max_sum[i]);
            }
        }
        cout<< result<<endl;
    }
}

#include<bits/stdc++.h>
using namespace std;
int n;
vector<int> record(21,0);
bool dp[20000007] = {false};
bool cmp(int a, int b)
{
    return a>b;
}

int main()
{
    cin>>n;
    int sum = 0;
    for(int i = 0; i<n;i++)
    {
        cin>>record[i];
        sum += record[i];
    }
    int mid = sum >>1;
    if(sum & 1)
        mid +=1;
    dp[0] = true;
    int result = 0;
    for(int i = 0; i<n; i++)
    {
        for(int j = mid; j>=record[i]; j--)
        {
            if(dp[j - record[i]])
            {
                dp[j] = true;
                result = max(result,j);
            }
        }
    }

    cout<<abs(sum - result - result)<<endl;
}