This page is still under construction.

Parts of this page are still being built. What you see may change.

King and Queen

Time limit2sMemory limit256 MB

Summary
Given an n by m board with a queen on (x, y), count the connected regions of cells the king (no diagonal moves) can reach without stepping on a queen-attacked cell, and print each region's size sorted.
Level

Medium6 of 10

Topics
Geometry, Math, Implementation
Solved
No attempts yet

Problem

After a long and exhausting chess battle, only a black king and a white queen remain on a board of n×mn \times m cells. Anyone who has played even a little chess knows that in this situation the king's life is in serious danger. The situation is made worse by the fact that the king is wounded and therefore cannot move diagonally. Thus, in one move the king can move to any cell sharing a side with his current cell. The queen, as a reminder, attacks any cell on the same vertical, horizontal, or diagonal line as herself.

The king knows that the queen is too lazy to even chase him. He is sure she will stay in the cell with coordinates (x,y)(x, y). This means the king can choose any cell on the board and then live out his whole life in the region of the board that contains that cell. A region of the board is a set of cells such that the wounded king can travel from any cell of the set to any other without passing through cells that the queen attacks.

Now the king wants to know the number of regions on the board and the size of each of them. Help him do this.

Input

The first line contains a single integer not exceeding 10410^4, the number of test cases. The descriptions of the test cases follow, one per line.

A test case consists of four integers nn, mm, xx, yy (1≤x≤n≤109,1≤y≤m≤109)(1 \le x \le n \le 10^9, 1 \le y \le m \le 10^9), the dimensions of the board and the coordinates of the cell where the queen stands.

Output

For each test case, print the answer in the following format. First print an integer xx, the number of regions on the board. Then print xx numbers, the sizes of those regions. Print the sizes in nondecreasing order. Separate the numbers with spaces or newlines.

Examples1

  1. Example 1

    Input
    3
5 5 1 3
3 3 2 2
5 5 3 3
    Expected output
    4 1 1 5 5
0
8 1 1 1 1 1 1 1 1