After choosing the city for building the nuclear power plant, Darkgy wants you estimate the security of the nuclear reactor of the nuclear power plant.

The nuclear reactor has N×M grids. Each grid can be empty, **uranium cell**, **integrated heat dispenser**, **cooling cell** or **upgrade cell**.

Uranium cell: Uranium cell can works for T ticks. At the beginning of each tick, an uranium cell will generate (1 + k) times uranium impulses (k is the amount of uranium cells whose Manhattan distance to this unranium cell is 1). An uranium impulses will generate 24 units heat, which means, if there are k uranium cells adjecent to an uranium cell, it will generate (1+k) ×24 units heat per tick.

The heat will be transmited to integrated heat dispensers and cooling cells **immediately** (the weight is the reciprocal of the length of the shortest path from the uranium cell to integrated heat dispensers or cooling cells which didn't go through any other integrated heat dispensers or cooling cells), if the heat cannot transmit to any integrated heat dispensers or cooling cells, the nuclear reactor will exploded and destroy the city.

Integrated heat dispenser: integrated heat dispenser will make itself and adjacent integrated heat dispensers and cooling cells (which Manhattan distance to it is 1) has equivalent heat at once **after the transmition of the heat from uranium cell finished.** At any time, if an integrated heat dispenser has more than Q units heat, it (include its heat) will disappear at once.

Cooling cell: Every tick after integrated heat dispenser worked, cooling cell will dissipate **at most** (8 + 2k) units heat of itself (k is the amount of upgrade cells which Manhattan distance to it is 1). At any time, if a cooling cell has more than Q units heat, it (include its heat) will disappear at once.

Upgrade Cell: can upgrade the ability of the adjacent cooling cell.

In a word, the whole process of each tick can be divided into three steps: Firstly, uranium cell generate heat and transmit to Integrated heat dispenser and cooling cell. Secondly, Integrated head dispenser swap the heat. At last, cooling cell dissipate the heat.

Input will consist of multiple test cases.

The first line of each test case contains four integers N, M, T, Q(0 ≤ N,M ≤ 20,0 ≤ T ≤ 10^{5},0 ≤ Q ≤ 10^{9}).

The next N lines, each line contains M characters, which means the designs of nuclear reactor ('.' indicates empty, 'U' indicates uranium cell, 'I' indicates integrated heat dispensers, 'C' indicates cooling cell and 'X' indicates upgrade cell).

提交代码