B: Hokkaido University Hard

Note

Please note that the question settings are the same as question A, except for the constraints.

story

Homura-chan, who passed Hokkaido University and is excited about the beginning of a new life. But in front of her, a huge campus awaits ...

"Eh ... I'm not in time for the next class ..."

problem

Hokkaido University Sapporo Campus is famous for being unusually large. The Sapporo campus is represented by rectangular squares with H squares vertically and W squares horizontally. We will use (i, j) to represent the cells that are i-mass from the north and j-mass from the west. There are several buildings on campus, with a'B'if there is a building in the location represented by the square (i, j) and a'.' If not, in c_ {i, j}.

Homura, a freshman at Hokkaido University, was surprised at the size of the campus and was worried about moving between buildings. So I was wondering how far the farthest of the two squares with the building were. Here we define the distance between two pairs of squares (i, j), (i', j') as | i-i'| + | j-j'|.

Homura found this problem difficult for him and asked his classmates for help. Please ask for an answer instead of Homura-chan.

Input format


H W
c_ {11} c_ {12} ... c_ {1W}
::
c_ {H1} c_ {H2} ... c_ {HW}


Constraint

* 2 \ leq H, W \ leq 10 ^ 3
* H and W are integers
* c_ {i, j} is either'B'or'.'.
* At least two of c_ {i, j} are'B'.



Output format

Print the integer that represents the answer on one line.

Input example 1


3 3
B.B
..B
.BB


Output example 1


Four

* The longest is between the two points (1,1) and (3,3).



Input example 2


4 3
B ..
B ..
...
...


Output example 2


1

* Adjacent positions may be the longest.



Input example 3


6 6
... B ..
B.B.B.
.B.B.B
... B.B
.B..B.
..B ...


Output example 3


7





Example

Input

3 3
B.B
..B
.BB


Output

4
#pragma GCC optimize ("O3")
#pragma GCC target ("tune=native")
#pragma GCC target ("avx")

#include <bits/stdc++.h>

// 汎用マクロ
#define ALL_OF(x) (x).begin(), (x).end()
#define REP(i,n) for (long long i=0, i##_len=(n); i<i##_len; i++)
#define RANGE(i,is,ie) for (long long i=(is), i##_end=(ie); i<=i##_end; i++)
#define DSRNG(i,is,ie) for (long long i=(is), i##_end=(ie); i>=i##_end; i--)
#define UNIQUE(v) { sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end()); }
template<class T> bool chmax(T &a, const T &b) {if (a < b) {a = b; return true;} return false; }
template<class T> bool chmin(T &a, const T &b) {if (a > b) {a = b; return true;} return false; }
#define INF 0x7FFFFFFF
#define LINF 0x7FFFFFFFFFFFFFFFLL
#define Yes(q) (q ? "Yes" : "No")
#define YES(q) (q ? "YES" : "NO")
#define DUMP(q) cerr << "[DEBUG] " #q ": " << (q) << " at " __FILE__ ":" << __LINE__ << endl
#define DUMPALL(q) { cerr << "[DEBUG] " #q ": ["; REP(dumpall_i, (q).size()) { cerr << q[dumpall_i] << (dumpall_i == (q).size() - 1 ? "" : ", "); } cerr << "] at " __FILE__ ":" << __LINE__ << endl; }
template<class T> T gcd(const T &a, const T &b) { return a < b ? gcd(b, a) : b ? gcd(b, a % b) : a; }
template<class T> T lcm(const T &a, const T &b) { return a / gcd(a, b) * b; }

// gcc拡張マクロ
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll

// エイリアス
using  ll = long long;
using ull = unsigned long long;
using  ld = long double;
using namespace std;

// モジュール


// 処理内容
int main() {
    
    ll h, w; cin >> h >> w;
    vector<string> c(h);
    REP(i, h) cin >> c[i];
    
    vector<ll> imin(w, INF), imax(w, -INF);
    REP(i, h) REP(j, w) {
        if (c[i][j] == 'B') {
            chmin(imin[j], i);
            chmax(imax[j], i);
        }
    }

    ll ans = 0;
    REP(j, w) RANGE(k, j, w-1) {

        if (imin[j] == INF || imin[k] == INF) continue;

        ll dj = k - j; // >= 0
        ll dimax = max({
            abs(imin[j] - imin[k]),
            abs(imin[j] - imax[k]),
            abs(imax[j] - imin[k]),
            abs(imax[j] - imax[k])
        });
        chmax(ans, dj + dimax);

    }

    cout << ans << endl;
    
}
