Description

Johnny just got a lot of sugar from his PaPa!

However, Johnny is too excited that he accidently fall and all of the sugar just fall onto the ground. 

PaPa is angry, and asked Johnny to clean the room up and take all his sugar away. 

After Johnny's begging, PaPa thought of a problem. If Johnny could solve it, PaPa may just forgive him.

The sugar now seperated on the ground. The ground is a 2D coordinate with n * n slots, each slot has several pieces of sugar. PaPa will give Johnny the number of pieces of sugar in each slot. Johnny needs to answer the maximum number of every row and the minimum number of every column, otherwise, he will be punished!

Johnny is a bad boy, he command you to help him, and if you do it well, he will not give you any sugar, but you'll receive an AC.

Input

The first line contains only one integer that indicates the number n.

The next n lines, each line contains n non-negitive integers, PaPa will give you the number of pieces of sugar in each slot.

1 <= n <=1000, each piece of sugar will not excceed 50000. 

Output

The first line, output the maximum number of each row. There should be n numbers.

The second line, output the minimum number of each column. There should be n numbers, too.

There should be a space next to each number except the last number, which means there should be no space at the end of each line.

Remember to output a '\n' at the end of the output. 

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

"Oh, no! The problem is so hard! No, no, no... Am I too stupid?"

"Hey, my code is right! Why do I always get a WA or TLE?"

"The method is difficult to understand, why are TAs always give us such a hard problem?"

"Did you heard that? I heard that the problem of the other professorss course is far more easier..." "Really? I should have chosen the other course..."

Yeah, we TA all know that it's hard for you to understand these new concepts. However, we do hope you to learn some knowledge that is important or useful. Such as "Prefix Sum", you can pre-calculate all the sum of (1,i) to get any sum of (i,j), which is far more faster than calculate the sum using for/while... right? 

What about gcd or fast power(快速冪)? I think all of you may learn the split phase division(輾轉相除法), so it should be not too hard to you guys to learn that, right? For the part of fpw(fast power), it's not too hard to realize how it works, which is also wonderful that we could calculate n^m or the n-th Fibonacci number so fast, even without include<moon>!

We do hope you guys could enjoy learning these interesting concepts instead of just taking the course, getting an A/A+, and treat this course as a part of your 4.3 GPA. 

If you don't want to learn these extra knowledge, or you're too busy to learn, you can just submit a brute-force solution without using any of the concepts above, you can still pass 3-5 testcases(only if the method is right).

So now, we're going to have another question. Don't worry, you can get an AC by brute force (though that would be a little difficult).

You guys have learned IEEE floating point number, right? If you forget it, rewind it, please. Our problem won't become easier for you :(

---

• You are given a IEEE-754 floating number with single precision(which is type "float" in C)
• You are going to output every bit of the number, from the largest bit to the smallest bit (including every 0)
• Note that scanf("%f", &x); will automatically parse scientific numbers into floating point number, so you don't have to implement this part.

Hint.1: You may solve this problem by using pointer tricks extremely easily. However, you can still solve this by using traditional way. :)

Hint.2: You may refer to this page to check the binary of a fp number.

Enjoy!

Input

The input contains multiple testcases, which means we'll input several floating point numbers, ended by EOF.

Note that there may be precision error due to the precision of floating point number. What we want you to output is the binary bits of the floating point number stored in C variable.

We recommand to use scanf as your input function.

You can take a look and observe the sample IO.

The range of the floating point number is -10²⁰ ~ 10²⁰.

Output

Output every bit of the floating point number. Remember to print a '\n' at the end of every output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Recently, Gilgamesh found that he's almost lack of swords in his vault, so he wants to forge a lot of swords with different shapes. He command you to forge for him!

Gilgamesh's sword can only be forged by triangle. Different triangle can be forged into a unique sword. He will give you the intervals of the edges of triangles, you have to calculate how many swords with different shape can he get?

Gilgamesh threats you with his "Gate of Babylon".

---

You are given four positive integer $A\le B\le C\le D$, you're going to count how many triangle that can be build by edges with length $x,\ y,\ z$, where $A\le x\le B,\ B\le y\le C,\ C\le z\le D$.

For example: $A=1,\ B=2,\ C=3,\ D=4$

You can build triangles with edges : $(x,y,z)\in \{(1,3,3),\ (2,2,3),\ (2,3,3),\ (2,3,4)\}$.

So the answer is 4.

Input

The first line contains one integer $T$, there are $T$ testcases below.

For each testcase, the four integer $A,\ B,\ C,\ D$ is given respectively.

$1\le T\le 100$.

$1\le A\le B\le C\le D\le 5\times 10^4$.

Output

For each testcase, output its answer, followed by a newline character.

Sample Input  Download

Sample Output  Download

Tags

Discuss