@file:Suppress("NOTHING_TO_INLINE", "EXPERIMENTAL_FEATURE_WARNING", "OVERRIDE_BY_INLINE")
//@file:OptIn(ExperimentalStdlibApi::class)

import java.io.PrintWriter
import kotlin.math.*
import kotlin.random.Random
import kotlin.collections.sort as _sort
import kotlin.collections.sortDescending as _sortDescending
import kotlin.io.println as iprintln


/** @author Spheniscine */
fun main() { _writer.solve(); _writer.flush() }
fun PrintWriter.solve() {
//    val startTime = System.nanoTime()

    val numCases = 1//readInt()
    case@ for(case in 1..numCases) {
//        print("Case #$case: ")

        object {
            val n = readInt()
            val m = readInt()

            val S = Array(n) { CharArray(m) { readChar() }.also { readChar() } }

            inline fun forEachNeighbor(i: Int, j: Int, yield: (ni: Int, nj: Int, d: Char) -> Unit) {
                if(i > 0) yield(i-1, j, '^') // up / north
                if(i < n -1) yield(i+1, j, 'v') // down / south
                if(j > 0) yield(i, j-1, '<') // left / west
                if(j < m -1) yield(i, j+1, '>') // right / east
            }

            val src = n * m
            val snk = src + 1
            val D = Dinic(snk + 1, src, snk)

            inline fun v(i: Int, j: Int) = i*m+j

            init {
                for(i in 0 until n) for(j in 0 until m) if(S[i][j] == '.') {
                    val u = v(i, j)
                    if(i xor j and 1 == 0) {
                        D.addEdge(src, u, 1)
                        forEachNeighbor(i, j) { ni, nj, _ ->
                            if(S[ni][nj] == '.') {
                                val v = v(ni, nj)
                                D.addEdge(u, v, 1)
                            }
                        }
                    } else {
                        D.addEdge(u, snk, 1)
                    }
                }

                val ans = D.maxFlow()
                println(ans)

                val F = D.F
                for(i in 0 until n) for(j in 0 until m) if(S[i][j] == '.') {
                    val u = v(i, j)
                    run {
                        forEachNeighbor(i, j) { ni, nj, d ->
                            if (F[u][v(ni, nj)] != 0) {
                                S[i][j] = d
                                return@run
                            }
                        }
                    }
                }

                S.forEach(::println)
            }
        }
    }

//    iprintln("Time: ${(System.nanoTime() - startTime) / 1000000} ms")
}

typealias Cap = Int
const val inf = Int.MAX_VALUE

class Dinic(val n: Int, val s: Int, val t: Int) {
    var solved = false
    val C = Array(n) { IntIntMap() } // capacity
    val F = Array(n) { IntIntMap() } // flow

    fun addEdge(u: Int, v: Int, w: Cap) {
        C[u][v] = w
        C[v][u] = 0
    }
    fun addEdge2(u: Int, v: Int, w: Cap) {
        C[u][v] = w
        C[v][u] = w
    }

    fun solve() {
        if(solved) return
        solved = true

        val adj = Array(n) { C[it].keys() }

        while(true) {
            // bfs
            val L = IntArray(n) { -1 }
            val Q = IntDeque()
            Q.add(s)
            L[s] = 0

            while(Q.isNotEmpty()) {
                val u = Q.remove()
                for(v in adj[u]) if(L[v] == -1 && F[u][v] < C[u][v]) {
                    L[v] = L[u] + 1
                    Q.add(v)
                }
            }

            if(L[t] == -1) break

            // dfs
            val next = IntArray(n)

            val P = intListOf(s)

            p@ while (P.isNotEmpty()) {
                if(P.last() == t) {
                    var f = Cap.MAX_VALUE
                    for (i in 0 until P.lastIndex) {
                        val u = P[i]
                        val v = P[i + 1]
                        next[u]--
                        f = min(f, C[u][v] - F[u][v])
                    }

                    for (i in 0 until P.lastIndex) {
                        val u = P[i]
                        val v = P[i + 1]
                        F[u][v] += f
                        F[v][u] -= f
                    }

                    P.clear()
                    P.add(s)
                }

                val u = P.last()

                val m = adj[u].size
                while (next[u] < m) {
                    val v = adj[u][next[u]++]
                    if (L[v] == L[u] + 1 && F[u][v] < C[u][v]) {
                        P.add(v)
                        continue@p
                    }
                }

                P.pop()
            }
        }
    }

    fun maxFlow(): Cap {
        solve()
        return F[s].values().sum()
    }
}

typealias IntIntMap = _Ez_Int__Int_HashMap
inline operator fun IntIntMap.set(key: Int, value: Int) { put(key, value) }

class _Ez_Int__Int_HashMap(capacity: Int = DEFAULT_CAPACITY) :
    _Ez_Int__Int_Map {
    companion object {
        private const val DEFAULT_CAPACITY = 8
        // There are three invariants for size, removedCount and arraysLength:
// 1. size + removedCount <= 1/2 arraysLength
// 2. size > 1/8 arraysLength
// 3. size >= removedCount
// arraysLength can be only multiplied by 2 and divided by 2.
// Also, if it becomes >= 32, it can't become less anymore.
        private const val REBUILD_LENGTH_THRESHOLD = 32
        private const val HASHCODE_INITIAL_VALUE = -0x7ee3623b
        private const val HASHCODE_MULTIPLIER = 0x01000193
        private const val FREE: Byte = 0
        private const val REMOVED: Byte = 1
        private const val FILLED: Byte = 2
        private const /*T2*/ val   /*T2*/DEFAULT_NULL_VALUE = 0
        private val hashSeed = random.nextInt()
    }

    private lateinit /*T1*/  var keys: IntArray
    private lateinit /*T2*/  var values: IntArray
    private lateinit var status: ByteArray
    override var size = 0
        private set
    private var removedCount = 0
    private var mask = 0

    constructor(map: _Ez_Int__Int_Map) : this(map.size) {
        val it = map.iterator()
        while (it.hasNext()) {
            put(it.key, it.value)
            it.next()
        }
    }

    constructor(javaMap: Map<Int, Int>) : this(javaMap.size) {
        for ((key, value) in javaMap) {
            put(key, value)
        }
    }

    private fun getStartPos(h: Int): Int {
        var x = h xor hashSeed
        x = (x xor (x ushr 16)) * 0x7feb352d
        x = (x xor (x ushr 15)) * 0x846ca68b.toInt()
        return (x xor (x ushr 16)) and mask
    }

    override fun isEmpty(): Boolean = size == 0

    override fun containsKey( /*T1*/
        /*T1*/key: Int
    ): Boolean {
        var pos = getStartPos(key)
        while (status[pos] != FREE) {
            if (status[pos] == FILLED && keys[pos] == key) {
                return true
            }
            pos = pos + 1 and mask
        }
        return false
    }

    /*T2*/ override fun  /*T2*/get( /*T1*/
        /*T1*/key: Int
    ): Int {
        var pos = getStartPos(key)
        while (status[pos] != FREE) {
            if (status[pos] == FILLED && keys[pos] == key) {
                return values[pos]
            }
            pos = pos + 1 and mask
        }
        return DEFAULT_NULL_VALUE
    }

    /*T2*/ override fun  /*T2*/put( /*T1*/
        /*T1*/key: Int,  /*T2*/
        /*T2*/value: Int
    ): Int {
        var pos = getStartPos(key)
        while (status[pos] == FILLED) {
            if (keys[pos] == key) {
                val   /*T2*/oldValue = values[pos]
                values[pos] = value
                return oldValue
            }
            pos = pos + 1 and mask
        }
        if (status[pos] == FREE) {
            status[pos] = FILLED
            keys[pos] = key
            values[pos] = value
            size++
            if ((size + removedCount) * 2 > keys.size) {
                rebuild(keys.size * 2) // enlarge the table
            }
            return DEFAULT_NULL_VALUE
        }
        val removedPos = pos
        pos = pos + 1 and mask
        while (status[pos] != FREE) {
            if (status[pos] == FILLED && keys[pos] == key) {
                val   /*T2*/oldValue = values[pos]
                values[pos] = value
                return oldValue
            }
            pos = pos + 1 and mask
        }
        status[removedPos] = FILLED
        keys[removedPos] = key
        values[removedPos] = value
        size++
        removedCount--
        return DEFAULT_NULL_VALUE
    }

    /*T2*/ override fun  /*T2*/remove( /*T1*/
        /*T1*/key: Int
    ): Int {
        var pos = getStartPos(key)
        while (status[pos] != FREE) {
            if (status[pos] == FILLED && keys[pos] == key) {
                val   /*T2*/removedValue = values[pos]
                status[pos] = REMOVED
                size--
                removedCount++
                if (keys.size > REBUILD_LENGTH_THRESHOLD) {
                    if (8 * size <= keys.size) {
                        rebuild(keys.size / 2) // compress the table
                    } else if (size < removedCount) {
                        rebuild(keys.size) // just rebuild the table
                    }
                }
                return removedValue
            }
            pos = pos + 1 and mask
        }
        return DEFAULT_NULL_VALUE
    }

    override fun clear() {
        if (keys.size > REBUILD_LENGTH_THRESHOLD) {
            initEmptyTable(REBUILD_LENGTH_THRESHOLD)
        } else {
            status.fill(FREE)
            size = 0
            removedCount = 0
        }
    }

    /*T1*/ override fun keys(): IntArray { /*T1*/
        val result = IntArray(size)
        var i = 0
        var j = 0
        while (i < keys.size) {
            if (status[i] == FILLED) {
                result[j++] = keys[i]
            }
            i++
        }
        return result
    }

    /*T2*/ override fun values(): IntArray { /*T2*/
        val result = IntArray(size)
        var i = 0
        var j = 0
        while (i < values.size) {
            if (status[i] == FILLED) {
                result[j++] = values[i]
            }
            i++
        }
        return result
    }

    override fun iterator(): _Ez_Int__Int_MapIterator {
        return _Ez_Int__Int_HashMapIterator()
    }

    private fun rebuild(newLength: Int) { /*T1*/
        val oldKeys = keys
        /*T2*/
        val oldValues = values
        val oldStatus = status
        initEmptyTable(newLength)
        for (i in oldKeys.indices) {
            if (oldStatus[i] == FILLED) {
                put(oldKeys[i], oldValues[i])
            }
        }
    }

    private fun initEmptyTable(length: Int) {
        keys = IntArray(length)
        values = IntArray(length)
        status = ByteArray(length)
        size = 0
        removedCount = 0
        mask = length - 1
    }

    override fun equals(other: Any?): Boolean {
        if (this === other) return true
        if (other == null || javaClass != other.javaClass) return false
        val that = other as _Ez_Int__Int_HashMap
        if (size != that.size) {
            return false
        }
        for (i in keys.indices) {
            if (status[i] == FILLED) { /*T2*/
                val   /*T2*/thatValue = that[keys[i]]
                if (thatValue != values[i]) {
                    return false
                }
            }
        }
        return true
    }

    override fun hashCode(): Int {
        val entryHashes = IntArray(size)
        run {
            var i = 0
            var j = 0
            while (i < status.size) {
                if (status[i] == FILLED) {
                    var hash = HASHCODE_INITIAL_VALUE
                    hash =
                        (hash xor keys[i]) * HASHCODE_MULTIPLIER
                    hash =
                        (hash xor values[i]) * HASHCODE_MULTIPLIER
                    entryHashes[j++] = hash
                }
                i++
            }
        }
        entryHashes.sort()
        var hash = HASHCODE_INITIAL_VALUE
        for (i in 0 until size) {
            hash = (hash xor entryHashes[i]) * HASHCODE_MULTIPLIER
        }
        return hash
    }

    override fun toString(): String {
        val sb = StringBuilder()
        sb.append('{')
        for (i in keys.indices) {
            if (status[i] == FILLED) {
                if (sb.length > 1) {
                    sb.append(", ")
                }
                sb.append(keys[i])
                sb.append('=')
                sb.append(values[i])
            }
        }
        sb.append('}')
        return sb.toString()
    }

    private inner class _Ez_Int__Int_HashMapIterator : _Ez_Int__Int_MapIterator {
        private var curIndex = 0
        override fun hasNext(): Boolean {
            return curIndex < status.size
        }

        /*T1*/  /*T1*/
        override val key: Int
            /*T1*/
            get() {
                if (curIndex == keys.size) {
                    throw NoSuchElementException("Iterator doesn't have more entries")
                }
                return keys[curIndex]
            }

        /*T2*/  /*T2*/
        override val value: Int
            /*T2*/
            get() {
                if (curIndex == values.size) {
                    throw NoSuchElementException("Iterator doesn't have more entries")
                }
                return values[curIndex]
            }

        override fun next() {
            if (curIndex == status.size) {
                return
            }
            curIndex++
            while (curIndex < status.size && status[curIndex] != FILLED) {
                curIndex++
            }
        }

        init {
            while (curIndex < status.size && status[curIndex] != FILLED) {
                curIndex++
            }
        }
    }

    init {
        require(capacity >= 0) { "Capacity must be non-negative" }
        // Actually we need 4x more memory
        var length = 4 * max(1, capacity)
        if (length and length - 1 != 0) {
            length = Integer.highestOneBit(length) shl 1
        }
        // Length is a power of 2 now
        initEmptyTable(length)
    }
}

interface _Ez_Int__Int_Map {
    // TODO null issues, e.g. when there is no value for a certain key - consider returning special 'null value'
    /**
     * Returns the size of the map, i.e. the number of entries (key-value pairs) in it.
     * @return the size of the map
     */
    val size: Int

    /**
     * Checks if the map contains at least one entry (key-value pair).
     * @return `true` if the map doesn't contain any entries, `false` otherwise
     */
    fun isEmpty(): Boolean

    /**
     * Checks if the map contains the entry with the specified key.
     * @param key the key to be checked
     * @return `true` if the map contains the entry with the specified key, `false` otherwise
     */
    fun containsKey( /*T1*/
        /*T1*/key: Int
    ): Boolean

    /**
     * Returns the value for the specified key. If the map doesn't contain the entry with the specified key, this
     * method can return everything, but sets the special flag, you should check it immediately after using get() this
     * way:
     * <pre>
     * if (map.returnedNull()) {
     * // The map doesn't contain the entry with the specified key.
     * // Take it into account and don't use the value returned by get().
     * } else {
     * // The call of get() was successful.
     * // You can use the value returned by get().
     * }
    </pre> *
     * @param key the key of the entry
     * @return the value for the specified key
     * @see .returnedNull
     */
/*T2*/
    operator fun  /*T2*/get( /*T1*/
        /*T1*/key: Int
    ): Int

    /**
     * Puts the specified key-value pair into the map. That is, if the map already contains the entry for the specified
     * key, the previous value is overridden by the new one, and if it doesn't, the new entry is created. In the first
     * case, the previous value is returned, and in the second case it can return everything, but the special flag is
     * set. If you are going to use the returned value, you should check it immediately after using put() this way:
     * <pre>
     * if (map.returnedNull()) {
     * // The map didn't contain the entry with the specified key. New entry was created.
     * // Take it into account and don't use the value returned by put().
     * } else {
     * // The map contained the entry with the specified key. The value was overridden.
     * // You can use the previous value returned by put().
     * }
    </pre> *
     * @param key the key of the entry
     * @param value the value of the entry
     * @return the previous value for the specified key
     * @see .returnedNull
     */
/*T2*/
    fun  /*T2*/put( /*T1*/
        /*T1*/key: Int,  /*T2*/
        /*T2*/value: Int
    ): Int

    /**
     * Removes the entry with the specified key from the map. This method returns the value of the removed entry,
     * however, if the map doesn't contain the entry with the specified key, it can return everything, but sets the
     * special flag, you should check it immediately after using remove() this way:
     * <pre>
     * if (map.returnedNull()) {
     * // The map doesn't contain the entry with the specified key. Nothing has been removed.
     * // Take it into account and don't use the value returned by remove().
     * } else {
     * // The call of remove() was successful.
     * // You can use the value returned by remove().
     * }
    </pre> *
     * @param key the key of the entry to be removed
     * @return the value of the removed entry
     * @see .returnedNull
     */
/*T2*/
    fun  /*T2*/remove( /*T1*/
        /*T1*/key: Int
    ): Int

    /**
     * Removes all entries from the map.
     */
    fun clear()

    /**
     * Returns the array which contains all keys in this map. It is not guaranteed that the array will be ordered in
     * any particular order. However, two consecutive calls of `keys()` and [.values] methods return two
     * arrays related to each other such that for every index `i` the entry `(keys[i], values[i])` is
     * contained in the map. This method always allocates new array, so you can modify it and the original map won't
     * be changed, and vice versa.
     * @return the array which contains all keys in this map
     */
/*T1*/
    fun keys(): IntArray

    /**
     * Returns the array which contains all values in this map. It is not guaranteed that the array will be ordered in
     * any particular order. However, two consecutive calls of [.keys] and `values()` methods return two
     * arrays related to each other such that for every index `i` the entry `(keys[i], values[i])` is
     * contained in the map. This method always allocates new array, so you can modify it and the original map won't
     * be changed, and vice versa.
     * @return the array which contains all values in this map
     */
/*T2*/
    fun values(): IntArray

    /**
     * Returns the iterator which can be used to go through the entries of this map. It is not guaranteed that the
     * iterator will return the entries in any particular order.
     * @return the iterator to go through the entries of this map
     */
    operator fun iterator(): _Ez_Int__Int_MapIterator

    /**
     * Returns the hashcode of the map. If two maps are equal, their hashcodes are also equal. If the hashcodes of two
     * maps are different, these maps are also different. Please note that different maps can have equal hashcodes,
     * though the probability of this fact is low.
     * @return the hashcode of the map
     */
    override fun hashCode(): Int

    /**
     * Returns the human-readable string representation of the map.
     * @return the string representation of the map
     */
    override fun toString(): String
}

interface _Ez_Int__Int_MapIterator {
    /**
     * Checks if the iterator has more available entries.
     * @return `true` if the iterator has more entries, `false` otherwise
     */
    operator fun hasNext(): Boolean

    /**
     * Returns the key of the entry at which the iterator currently points.
     * @return the key of the entry at which the iterator currently points
     * @throws java.util.NoSuchElementException if the iterator doesn't have more entries
     */
/*T1*/  /*T1*/
    val key: Int

    /**
     * Returns the value of the entry at which the iterator currently points.
     * @return the value of the entry at which the iterator currently points
     * @throws java.util.NoSuchElementException if the iterator doesn't have more entries
     */
/*T2*/  /*T2*/
    val value: Int

    /**
     * Moves the iterator to the next entry in the map. If there are no remaining entries, does nothing.
     */
    operator fun next()
}

inline fun IntIntMap.forEach(act: (key: Int, value: Int) -> Unit) {
    val ite = iterator()
    while(ite.hasNext()) {
        act(ite.key, ite.value)
        ite.next()
    }
}

class IntList(initialCapacity: Int = 12) {
    private var _arr = IntArray(initialCapacity)
    private val capacity get() = _arr.size
    var size = 0
        private set
    inline val lastIndex get() = size - 1
    inline val indices get() = 0 until size

    constructor(copyFrom: IntArray): this(copyFrom.size) { copyFrom.copyInto(_arr); size = copyFrom.size }
    constructor(copyFrom: Collection<Int>): this(copyFrom.size) { _arr = copyFrom.toIntArray(); size = copyFrom.size }

    fun contentEquals(other: IntList): Boolean {
        return this === other || size == other.size && indices.all { this[it] == other[it] }
    }

    private fun grow(minCapacity: Int = 8) {
        val newCapacity = maxOf(minCapacity, capacity + (capacity shr 1))
        _arr = _arr.copyOf(newCapacity)
    }

    fun ensureCapacity(minCapacity: Int) { if(capacity < minCapacity) grow(minCapacity) }

    operator fun get(index: Int): Int {
        require(index in 0 until size)
        return _arr[index]
    }

    operator fun set(index: Int, value: Int) {
        require(index in 0 until size)
        _arr[index] = value
    }

    fun add(value: Int) {
        if(size == capacity) grow()
        _arr[size++] = value
    }

    fun addAll(list: IntList) {
        ensureCapacity(size + list.size)
        list._arr.copyInto(_arr, size, 0, list.size)
        size += list.size
    }

    fun add(index: Int, element: Int) {
        if(size == capacity) grow()
        _arr.copyInto(_arr, index + 1, index, size)
        size++
        set(index, element)
    }

    fun clear() { size = 0 }

    fun removeAt(index: Int): Int {
        val e = get(index)
        _arr.copyInto(_arr, index, index + 1, size)
        size--
        return e
    }

    operator fun iterator() = object: IntIterator() {
        private var pos = 0
        override fun hasNext() = pos < size
        override fun nextInt() = get(pos++)
    }

    inline fun isEmpty() = size == 0
    inline fun isNotEmpty() = size != 0

    fun pop() = _arr[--size]

    fun popToSize(s: Int) { if(s < size) size = s }

    fun swap(i: Int, j: Int) { val t = this[i]; this[i] = this[j]; this[j] = t }
    fun reverse() {
        for(i in 0 until size / 2) swap(i, lastIndex - i)
    }

    fun shuffle(rnd: Random = random) = _shuffle(rnd, _arr::get, _arr::set, size)
    fun sort() { shuffle(); _arr._sort(0, size) }
    fun sortDescending() { sort(); reverse() }

    fun joinToString(separator: CharSequence) = if(size == 0) "" else let {
        buildString {
            append(it[0])
            for (i in 1 until size) {
                append(separator).append(it[i])
            }
        }
    }

    override fun toString() = "[" + joinToString(", ") + "]"

    fun toIntArray() = _arr.copyOf(size)
    fun toList() = List(size, ::get)

    inline fun first() = get(0)
    inline fun last() = get(lastIndex)
}

inline fun IntList(size: Int, init: (Int) -> Int) = IntList(size).apply {
    for(i in 0 until size) { add(init(i)) }
}
inline fun IntArray.toIntList() = IntList(this)
inline fun Collection<Int>.toIntList() = IntList(this)
inline fun intListOf(vararg values: Int) = IntList(values)

fun IntList.max() = (1 until size).fold(this[0]) { acc, i -> max(acc, this[i]) }
fun IntList.min() = (1 until size).fold(this[0]) { acc, i -> min(acc, this[i]) }
fun IntList.getOrNull(i: Int) = if(i in indices) get(i) else null
inline fun IntList.count(predicate: (Int) -> Boolean) = indices.count { predicate(this[it]) }
fun IntList.copyOf() = IntList(size, ::get)


class IntDeque(capacity: Int = 12){
    private var arr = IntArray(capacity)
    var size = 0
        private set
    inline val lastIndex get() = size - 1
    inline val indices get() = 0 until size

    private inline val capacity get() = arr.size

    inline fun isEmpty() = size == 0
    inline fun isNotEmpty() = size != 0

    private var head = 0

    private fun grow(minCapacity: Int = 8) {
        val newCapacity = maxOf(minCapacity, capacity + (capacity shr 1))
        val new = IntArray(newCapacity)
        for(i in 0 until size) new[i] = get(i)
        arr = new
        head = 0
    }

    private fun incHead() {
        head++
        if(head == capacity) head = 0
    }

    private fun decHead() {
        if(head == 0) head = capacity - 1
        else head--
    }

    private fun index(i: Int) = (head + i).let { if(it >= capacity) it - capacity else it }

    fun add(index: Int, element: Int) {
        if(size == capacity) grow()
        if(index < size / 2) {
            decHead()
            size++
            for(i in 0 until index) {
                set(i, get(i+1))
            }
        } else {
            size++
            for(i in size - 2 downTo index) {
                set(i+1, get(i))
            }
        }
        set(index, element)
    }

    fun addLast(e: Int) {
        if(size == capacity) grow()
        arr[index(size)] = e
        size++
    }
    inline fun add(e: Int) = addLast(e)

    val first get() = get(0)
    val last get() = get(lastIndex)

    fun removeFirst(): Int {
        val e = get(0)
        incHead()
        size--
        return e
    }
    inline fun remove() = removeFirst()
    fun removeLast(): Int {
        val e = get(lastIndex)
        size--
        return e
    }

    fun addFirst(e: Int) {
        if(size == capacity) grow()
        decHead()
        arr[head] = e
        size++
    }

    operator fun get(index: Int): Int {
        require(index in 0 until size)
        return arr[index(index)]
    }

    fun removeAt(index: Int): Int {
        val e = get(index)
        if(index < size / 2) {
            for(i in index - 1 downTo 0) {
                set(i+1, get(i))
            }
            incHead()
        } else {
            for(i in index until size - 1) {
                set(i, get(i+1))
            }
        }
        size--
        return e
    }

    operator fun set(index: Int, element: Int): Int {
        val old = get(index)
        arr[index(index)] = element
        return old
    }

    operator fun iterator() = object: IntIterator() {
        var i = 0
        override fun hasNext(): Boolean = i < size
        override fun nextInt(): Int = get(i++)
    }
}

/** IO */
//@JvmField val INPUT = File("input.txt").inputStream()
//@JvmField val OUTPUT = File("output.txt").outputStream()
@JvmField val INPUT = System.`in`
@JvmField val OUTPUT = System.out

const val _BUFFER_SIZE = 1 shl 16
@JvmField val _buffer = ByteArray(_BUFFER_SIZE)
@JvmField var _bufferPt = 0
@JvmField var _bytesRead = 0

tailrec fun readChar(): Char {
    if(_bufferPt == _bytesRead) {
        _bufferPt = 0
        _bytesRead = INPUT.read(_buffer, 0, _BUFFER_SIZE)
    }
    return if(_bytesRead < 0) Char.MIN_VALUE
    else {
        val c = _buffer[_bufferPt++].toChar()
        if (c == '\r') readChar()
        else c
    }
}

fun readLine(): String? {
    var c = readChar()
    return if(c == Char.MIN_VALUE) null
    else buildString {
        while(c != '\n' && c != Char.MIN_VALUE) {
            append(c)
            c = readChar()
        }
    }
}
fun readLn() = readLine()!!

fun read() = buildString {
    var c = readChar()
    while(c <= ' ') {
        if(c == Char.MIN_VALUE) return@buildString
        c = readChar()
    }
    do {
        append(c)
        c = readChar()
    } while(c > ' ')
}
fun readInt() = read().toInt()
fun readDouble() = read().toDouble()
fun readLong() = read().toLong()
fun readStrings(n: Int) = List(n) { read() }
fun readLines(n: Int) = List(n) { readLn() }
fun readInts(n: Int) = List(n) { read().toInt() }
fun readIntArray(n: Int) = IntArray(n) { read().toInt() }
fun readDoubles(n: Int) = List(n) { read().toDouble() }
fun readDoubleArray(n: Int) = DoubleArray(n) { read().toDouble() }
fun readLongs(n: Int) = List(n) { read().toLong() }
fun readLongArray(n: Int) = LongArray(n) { read().toLong() }

@JvmField val _writer = PrintWriter(OUTPUT, false)

/** shuffles and sort overrides to avoid quicksort attacks */
private inline fun <T> _shuffle(rnd: Random, get: (Int) -> T, set: (Int, T) -> Unit, size: Int) {
    // Fisher-Yates shuffle algorithm
    for (i in size - 1 downTo 1) {
        val j = rnd.nextInt(i + 1)
        val temp = get(i)
        set(i, get(j))
        set(j, temp)
    }
}

@JvmField var _random: Random? = null
val random get() = _random ?: Random(0x594E215C123 * System.nanoTime()).also { _random = it }

fun IntArray.shuffle(rnd: Random = random) = _shuffle(rnd, ::get, ::set, size)
fun IntArray.sort() { shuffle(); _sort() }
fun IntArray.sortDescending() { shuffle(); _sortDescending() }

fun LongArray.shuffle(rnd: Random = random) = _shuffle(rnd, ::get, ::set, size)
fun LongArray.sort() { shuffle(); _sort() }
fun LongArray.sortDescending() { shuffle(); _sortDescending() }

fun DoubleArray.shuffle(rnd: Random = random) = _shuffle(rnd, ::get, ::set, size)
fun DoubleArray.sort() { shuffle(); _sort() }
fun DoubleArray.sortDescending() { shuffle(); _sortDescending() }

fun CharArray.shuffle(rnd: Random = random) = _shuffle(rnd, ::get, ::set, size)
inline fun CharArray.sort() { _sort() }
inline fun CharArray.sortDescending() { _sortDescending() }

inline fun <T: Comparable<T>> Array<out T>.sort() = _sort()
inline fun <T: Comparable<T>> Array<out T>.sortDescending() = _sortDescending()
inline fun <T: Comparable<T>> MutableList<out T>.sort() = _sort()
inline fun <T: Comparable<T>> MutableList<out T>.sortDescending() = _sortDescending()

fun `please stop removing these imports IntelliJ`() { iprintln(max(1, 2)) }

/** additional commons */
inline fun <T> Iterable<T>.sumByLong(func: (T) -> Long) = fold(0L) { acc, t -> acc + func(t) }
inline fun <T> Sequence<T>.sumByLong(func: (T) -> Long) = fold(0L) { acc, t -> acc + func(t) }
inline fun <T> Array<T>.sumByLong(func: (T) -> Long) = fold(0L) { acc, t -> acc + func(t) }
fun IntArray.sumLong() = fold(0L, Long::plus)


Measured memory_bytes: 57392