Polish Flag

Time limit2sMemory limit128 MB

Summary
Three children grow regions of blocks from three fixed edges with priority rules and simultaneous expansion each turn; count each child's white (top) and red (bottom) cells.
Level

Hard8 of 10

Topics
Simulation, Geometry, Math, Implementation
Solved
No attempts yet

Problem

Three children -- Lucy, Bob, and Roy -- are building a Polish flag out of unit square blocks. The flag is a rectangle 3n3n blocks wide and 2n2n blocks high, where nn is a positive integer. It consists of 3n23n^2 white blocks and 3n23n^2 red blocks, and the board has 6n26n^2 slots in total. The white blocks must fill the top nn rows and the red blocks must fill the bottom nn rows. Rows are numbered from 11 to 2n2n from top to bottom, and columns from 11 to 3n3n from left to right. A slot's position is written as (column, row).

The children lay blocks in turns (all three act during each turn). In the first turn Lucy puts a block on the left edge at (1,l)(1, l), Bob puts a block on the bottom edge at (b,2n)(b, 2n), and Roy puts a block on the right edge at (3n,r)(3n, r), where 1≤l,r<2n1 \le l, r < 2n and 1<b<3n1 < b < 3n.

In every later turn a child may put a block into a slot only if that slot is empty and would be adjacent to one of the blocks that same child placed in the immediately preceding turn. (Two blocks are adjacent if they share a side.) In each turn every child places as many blocks as possible. Only one block may go into a slot. If two or more children want to place a block into the same slot in the same turn, Lucy has the highest priority, then Bob, and Roy has the lowest.

For each child, compute how many blocks of each color they end up placing. A block's color is fixed by the slot it occupies: cells in the top nn rows are white and cells in the bottom nn rows are red.

Input

The first and only line contains four integers nn, ll, bb, rr separated by single spaces, with 1≤n≤1091 \le n \le 10^9, 1≤l,r<2n1 \le l, r < 2n, and 1<b<3n1 < b < 3n. In 50% of the test cases nn does not exceed 100100.

Output

Print a single line with six integers separated by single spaces. The first and second are the numbers of white and red blocks that Lucy needs; the third and fourth are the numbers of white and red blocks that Bob needs; the fifth and sixth are the numbers of white and red blocks that Roy needs.

Hint

Examples2

  1. Example 1

    Input
    2 2 3 1
    
    Expected output
    7 3 0 8 5 1
    
  2. Example 2

    Input
    1 1 2 1
    
    Expected output
    2 1 0 2 1 0