考虑一个事实：对于 $x,y\geq 0$ 满足 $3^{x}+3^{x+2y}\geq 2\cdot 3^{x+y}$。

这告诉我们什么呢？将任务尽可能平均分配是最优的。我们先暂时忽略每天只能造整数个题的限制，考虑每天可以造任意实数个题。

所以如果只有一个条件，前 $x$ 天造好的数据数量应该是一个关于 $x$ 的一次函数。

现在考虑如果我们有很多条件，第一天应该造多少数据呢？答案是所有条件对应的一次函数中斜率的最大值。因为如果你没造到显然某一天要造更多数据，而造多了某一天可以少造一点。

于是我们去掉第一天重新考虑所有限制，不断求解直到所有条件都被满足。回顾这个过程……我们其实对所有条件求出了它们的凸壳。

那么将答案推回整数就很简单了，对于凸壳的每一段，我们的最优决策显然是选择一些 $\lfloor{\frac{\Delta y}{\Delta x}}\rfloor$ 和 $\lceil{\frac{\Delta y}{\Delta x}}\rceil$ 来满足了，它的权值和也容易计算。

维护凸壳就非常简单了！直接用 std::set 找新点在凸壳上前后的点，然后不断弹出删掉的点即可。

时间复杂度 $O(n\log n)$。

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
const int p=1e9+7;
int qp(int x,int y)
{
    if(y<0) return 0;
    int res=1;
    for(int t=x; y; y>>=1,t=1ll*t*t%p)
        if(y&1) res=1ll*res*t%p;
    return res;
}
int F(int x,int y)
{
    if(x==0) return 0;
    if(y<0) return 0;
    int g=y/x,q=y%x;
    return (q*qp(3,g)+(x-q)*qp(3,g-1))%p;
}
signed main()
{
    int n=read(),ans=0;
    set<pair<int,int>> st;
    st.insert({0,0});
    for(int i=1; i<=n; ++i)
    {
        int x=read(),y=read();
        if(st.count({x,y}))
        {
            printf("%lld\n",ans);
            continue;
        }
        auto nxt=st.lower_bound({x,y});
        if(nxt!=st.end())
        {
            auto pre=prev(nxt);
            auto [x1,y1]=*nxt;
            auto [x0,y0]=*pre;
            if((y-y0)*(x1-x0)<=(y1-y0)*(x-x0)) 
            {
                printf("%lld\n",ans);
                continue;
            }
            st.insert({x,y});
            ans=(ans+p-F(x1-x0,y1-y0))%p;
            ans=(ans+F(x-x0,y-y0))%p,
            ans=(ans+F(x1-x,y1-y))%p;
        }
        else
        {
            auto pre=prev(nxt);
            auto [x0,y0]=*pre;
            st.insert({x,y}),
            ans=(ans+F(x-x0,y-y0))%p;
        }
        while(1)
        {
            auto pre=prev(st.find({x,y}));
            if(pre==st.begin()) break;
            auto [x1,y1]=*pre;
            auto [x0,y0]=*prev(pre);
            if((y1-y0)*(x-x0)<=(y-y0)*(x1-x0))
            {
                ans=(ans+p-F(x1-x0,y1-y0))%p,
                ans=(ans+p-F(x-x1,y-y1))%p,
                ans=(ans+F(x-x0,y-y0))%p,
                st.erase(pre);
            }
            else break;
        }
        while(1)
        {
            auto nxt=next(st.find({x,y}));
            if(nxt==st.end()) break;
            if(next(nxt)==st.end()) break;
            auto [x0,y0]=*nxt;
            auto [x1,y1]=*next(nxt);
            if((y0-y)*(x1-x)<=(y1-y)*(x0-x))
            {
                ans=(ans+p-F(x1-x0,y1-y0))%p,
                ans=(ans+p-F(x0-x,y0-y))%p,
                ans=(ans+F(x1-x,y1-y))%p,
                st.erase(nxt);
            }
            else break;
        }
        printf("%lld\n",ans);
    }
    return 0;
}