There are n pirate chests buried in Byteland, labeled by 1,2,…,n. The i-th chest’s location is (xi,yi), and its value is wi, wi can be negative since the pirate can add some poisonous gases into the chest. When you open the i-th pirate chest, you will get wi value.

You want to make money from these pirate chests. You can select a rectangle, the sides of which are all paralleled to the axes, and then all the chests inside it or on its border will be opened. Note that you must open all the chests within that range regardless of their values are positive or negative. But you can choose a rectangle with nothing in it to get a zero sum.

Please write a program to find the best rectangle with maximum total value.

The first line of the input contains an integer T(1≤T≤100), denoting the number of test cases.

In each test case, there is one integer n(1≤n≤2000) in the first line, denoting the number of pirate chests.

For the next n lines, each line contains three integers xi,yi,wi(−109≤xi,yi,wi≤109), denoting each pirate chest.

It is guaranteed that ∑n≤10000.

分析

首先，我没做出来。

为了做课件又加了很多东西。

对于可以离线的区间询问问题，莫队算法提出了一种可以在$O(n\sqrt n)$(无修改)，$O(n^{5/3})$(带修改)内得出答案的方法。

主要的思路是对询问离线并分块，利用在2个区间间答案的快速转移（如果无法找到快速转移的方法，就没法用了）降低复杂度。

zz6d likes reading very much, so he bought a lot of books. One day, zz6d brought n books to a classroom in school. The books of zz6d is so popular that K students in the classroom want to borrow his books to read. Every book of zz6d has a number i (1<=i<=n). Every student in the classroom wants to get a continuous number books. Every book has a pleasure value,

Farmer John keeps a website called ‘FansBlog’ .Everyday , there are many people visited this blog.One day, he find the visits has reached P , which is a prime number.He thinks it is a interesting fact.And he remembers that the visits had reached another prime number.He try to find out the largest prime number Q ( Q < P ) ,and get the answer of Q! Module P.But he is too busy to find out the answer. So he ask you for help. ( Q! is the product of all positive integers less than or equal to n: n! = n * (n-1) * (n-2) * (n-3) *… * 3 * 2 * 1 . For example, 4! = 4 * 3 * 2 * 1 = 24 )

First line contains an number T(1<=T<=10) indicating the number of testcases. Then T line follows, each contains a positive prime number P (1e9≤p≤1e14)

一些结论 $N!$的质因数分解中某质数的指数为$\sum_{r=1}^{\inf}n/p^r $ 约数个数为质因数指数+1的乘积，和为质因数枚举指

集合挑选 从给定的N个集合中各挑出一个数并求和，求出前$K$大的$K$个和。 考虑如何从2个集合$A$,$B$中选出前$K$大。降序排序后$a_