Binary search tree (BST) update

Quido is developing a search engine which will manipulate millions of items in a relatively constrained memory space. To demonstrate the effectivity of his solution he is going to prepare a limited demo version which solves the task described bellow.

Denote by key(x) the value of the key of stored in the node x in an unempty BST.
Define the left order of the node x as the number of nodes in the BST which key value is smaller than key(x).
Operation Update(x, h) consists of two steps: In the first step, the node x is removed from the BST by standard operation Delete. In the second step, if the BST does not contain a node with key h then a new node with key h is inserted into the BST by standard operation Insert.

To specify the task unambiguously, Quido follows the rules:

The demo version generates a sequence of BST's (T1, T2, ..., TK), K > 0, the sizes of these BST's are denoted (in this order) by the symbols N1, N2, ..., NK.
The BST T1 is a balanced tree which depth is minimum possible and which contains all integer keys from the set {N, N+1, N+2, ..., N+2D − 2}, where N and D are positive integers. Note that N1 = 2D − 1.

Let A, B, M be fixed positive integers. The BST Tk+1 (k = 1, 2, ..., K−1) is obtained by modifying the BST Tk with one operation Update:



     


Image 1. Example of a BST before and after the operation Update(x, 15), the left order of x is 9. The left orders are written in a box at their respective nodes. The deleted and the inserted node are highlighted. Note the change of the left order of some other nodes.

The task

To check Quido's implementation we have to calculate the value of NK, the depth of TK and the number of those nodes in TK which depth is equal to the depth of TK.


Input

The input contains one text line with six positive integers K, N, D, A, B, M, separated by spaces. The meaning of the integers is described in the text above.
The value of K does not exceed 106, the value of D does not exceed 23, all other input values do not exceed 107.

Output

The otuput contains one text line with tree integers separated by spaces. The first integer is equal to NK, the second one is equal to the depth of TK and the third one is equal to the number of those nodes in TK which depth is equal to the depth of TK.
Let us remind you that the depth of the tree root is 0. You may suppose that the BST's T1, T2, ..., TK are unempty.

Example 1

Input
5 5 3 1 1 10
Output
5 3 1
The shape and the keys of the BST T5 are depicted bellow.
         ____[9]____
  ______[7]      [11]
 [1]___
     [6]

Example 2

Input
10 5 4 2 6 16
Output
10 4 1
The shape and the keys of the BST T10 are depicted bellow.
                ________[12]_______
      _________[10]___       ____[18]___
  ___[2]___         [11]    [13]      [19]
 [0]     [4]___
             [6]

Example 3

Input
100000 3 18 23233 2342 14301
Output
163112 18 118

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set