結果
| 問題 | No.1313 N言っちゃダメゲーム (4) |
| ユーザー |
 NokonoKotlin
|
| 提出日時 | 2020-12-13 03:37:12 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 9 ms / 2,000 ms |
| コード長 | 56,029 bytes |
| コンパイル時間 | 2,570 ms |
| コンパイル使用メモリ | 162,692 KB |
| 実行使用メモリ | 4,348 KB |
| 最終ジャッジ日時 | 2023-10-20 02:56:41 |
| 合計ジャッジ時間 | 3,876 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge11 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
4,348 KB |
| testcase_01 | AC | 2 ms
4,348 KB |
| testcase_02 | AC | 2 ms
4,348 KB |
| testcase_03 | AC | 2 ms
4,348 KB |
| testcase_04 | AC | 2 ms
4,348 KB |
| testcase_05 | AC | 2 ms
4,348 KB |
| testcase_06 | AC | 2 ms
4,348 KB |
| testcase_07 | AC | 2 ms
4,348 KB |
| testcase_08 | AC | 2 ms
4,348 KB |
| testcase_09 | AC | 2 ms
4,348 KB |
| testcase_10 | AC | 2 ms
4,348 KB |
| testcase_11 | AC | 2 ms
4,348 KB |
| testcase_12 | AC | 2 ms
4,348 KB |
| testcase_13 | AC | 7 ms
4,348 KB |
| testcase_14 | AC | 6 ms
4,348 KB |
| testcase_15 | AC | 7 ms
4,348 KB |
| testcase_16 | AC | 8 ms
4,348 KB |
| testcase_17 | AC | 8 ms
4,348 KB |
| testcase_18 | AC | 6 ms
4,348 KB |
| testcase_19 | AC | 5 ms
4,348 KB |
| testcase_20 | AC | 3 ms
4,348 KB |
| testcase_21 | AC | 5 ms
4,348 KB |
| testcase_22 | AC | 4 ms
4,348 KB |
| testcase_23 | AC | 5 ms
4,348 KB |
| testcase_24 | AC | 3 ms
4,348 KB |
| testcase_25 | AC | 6 ms
4,348 KB |
| testcase_26 | AC | 2 ms
4,348 KB |
| testcase_27 | AC | 5 ms
4,348 KB |
| testcase_28 | AC | 9 ms
4,348 KB |
| testcase_29 | AC | 9 ms
4,348 KB |
| testcase_30 | AC | 7 ms
4,348 KB |
| testcase_31 | AC | 9 ms
4,348 KB |
| testcase_32 | AC | 8 ms
4,348 KB |
| testcase_33 | AC | 7 ms
4,348 KB |
| testcase_34 | AC | 7 ms
4,348 KB |
| testcase_35 | AC | 6 ms
4,348 KB |
| testcase_36 | AC | 8 ms
4,348 KB |
| testcase_37 | AC | 7 ms
4,348 KB |
ソースコード
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include<queue>
using namespace std;
//conversion
//------------------------------------------
inline long long toint(string s) {long long v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}
//typedef
//------------------------------------------
typedef long long ll;
typedef long long LL;
typedef vector<int > vi;
typedef vector<long long > VLL;
typedef vector<long long > vll;
typedef vector<string > ves;
typedef vector<char > vech;
typedef pair<long long , long long> pll;
typedef pair<long long , long long> PLL;
typedef map<ll , ll >mll;
typedef map<int , int >mii;
typedef map<char , int >mci;
typedef map<char , ll >mcl;
//container util
//------------------------------------------
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define VECMAX(x) *max_element(ALL(x))
#define VECMIN(x) *min_element(ALL(x))
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
//#define MULTIPLE(i,n,k) for(int i = (k) ; i<(n) ; i+=k+1)//倍数ループ
//constant
//------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);
//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))
//debug
#define dump(x) cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define SIZEOF(x) sizeof(x)/sizeof(x[0])
const long long INF = 100000000000000;
const long long NINF = -100000000000000;
#define CIN(a) REP(i,a.size())cin >> a[i];
//-------------------------------------------------------------
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; }
ll nCr(ll n, ll r){
if ( r * 2 > n ) r = n - r;
ll dividend = 1;
ll divisor = 1;
for ( unsigned int i = 1; i <= r; ++i ) {
dividend *= (n-i+1);
divisor *= i;
}
return dividend / divisor;
}
//firstが最大値（最小値） , second が index
pair<LL , LL> maxP(vll a , ll size){
pair <ll , ll> p;
vll::iterator iter = max_element(a.begin() , a.end());
p.first = *iter;
p.second = distance(a.begin() , iter);
return p;
}
pair<LL , LL> minP(vll a , ll size){
pair <ll , ll> p;
vll::iterator iter = min_element(a.begin() , a.end());
p.first = *iter;
p.second = distance(a.begin() , iter);
return p;
}
ll sumL(vll a ,ll left, ll right){
ll sum = 0;
FOR(i , left , right){
sum += a[i];
}
return sum;
}
//sort済みのvll ; a のleft ~ rightにtがいくつあるか
ll counT(VLL a ,ll left , ll right , ll t ){
//sort(a.begin(),a.end());
return upper_bound(a.begin() + left , a.begin() + right,t)-lower_bound(a.begin() + left , a.begin() + right, t);
}
#define COUNT(a,b) counT((a),0,a.size(),(b))
#define MAX(x) maxP(x,x.size())
#define MIN(x) minP(x,x.size())
#define SUM(x) sumL(x,0,x.size())
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////
//-------------------DIVIDE----------------------
// DIV[i][j] は i の j分割数 j == 0 && i != 0 なら 0
//並び順を区別しない
ll DIV[1000+1][1000+1];
void divide(ll n ,ll m){
DIV[0][0]= 1;
FOR(i,1,n+1){
DIV[i][0] = 0;
}
REP(i,n+1){
DIV[i][1] = 1;
}
FOR(i,1,m+1){
FOR(t,0,n+1){
if(DIV[t][i] > 0)continue;
if(t>=i){
DIV[t][i]=DIV[t-i][i] + DIV[t][i-1];
}else{
DIV[t][i] = DIV[t][i-1];
}
}
}
}
#define DIVIDE(a,b) (DIV[a][b] - DIV[a][(b)-1]) //DIV[a-b][b]と同じ
//-------要素を見つける-----------
ll search(vll &a , ll n ){//a内のnのindexを返す
std::vector<ll>::iterator iter = std::find(a.begin(), a.end(), n);
size_t index = distance(a.begin(), iter);
return index;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////
//------------素数判定-----------------
//------------素数判定-----------------
class IsPrimeJudge{
public:
vector<bool> IS_PRIME_CONTAINER;
IsPrimeJudge(int max_):IS_PRIME_CONTAINER(max_, true){
max = max_;
}
int max;//この値-1まで素数判定する
//メモリを圧迫する可能性あり
void IsPrime_init(){
IS_PRIME_CONTAINER[0] = false;
IS_PRIME_CONTAINER[1] = false;
FOR(i,2,sqrt(max)+1){
if(IS_PRIME_CONTAINER[i]){
FOR(j,2,(max)/i + 1){
if(j*i<=max){
IS_PRIME_CONTAINER[i*j]=false;
}
}
}
}
}
inline bool IsPrime(ll num){
return IS_PRIME_CONTAINER[num];
}
};
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////
//---------ベルマンフォード----------
//頂点の値はindexとする
class Bellman{
//注意！！ーーーーーーーーーーーーーーーーーーーーーーーーーーーーー
//ベルマンフォードは遅いため、基本はダイクストラで書く！！
//しかし、辺の重みがマイナスの時はベルマンフォードを使う
public:
vll DIST;
//max は 頂点の数
Bellman(int max_ ):DIST(max_ , INF){
max = max_;
}
~Bellman(){
std::vector<ll>().swap(DIST);
}
int max;
//int max;//辺の数
//Bellman::E
struct edge{
//classの外で構造体Eを宣言するときは Bellman::E と宣言する
// from から toは一方通行であることに注意
ll from , to, cost;
};
//はじめに必ず初期化
void init(){
REP(i,max){
DIST[i] = INF;
}
}
vector<edge> G;
//G.push_back(Edge)で辺の情報を記憶させる
//startはindex(0から)
//start と 辺の数 m 辺の情報 x を入力
//頂点a,bが両方向に繋がってるなら、
//vector<Bellman::E>には(a,b,c)と(b,a,c)の両方を入れないといけない
void shortest(LL s){
REP(i,max){
DIST[i] = INF;
}
DIST[s] = 0;
while(1){
bool t = false;
REP(i,G.size()){
edge h = G[i];
if(DIST[h.from] != INF && DIST[h.to] > DIST[h.from] + h.cost){
//DIST[h.to] == DIST[h.from] + h.costを含めたらダメ、無限更新ループする
DIST[h.to] = DIST[h.from] + h.cost;
t = true;
}
}
if(!t){
break;
}
}
}
};
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////
//----------ダイクストラ------------
class dijkstra{
//頂点の値はindexとする
public:
int V;//Vは頂点の個数
//dijkstra::edge
struct edge {
int to;
int cost;
};
public:
// G[i]には頂点iから出る辺の情報が入ってる
vll dist;//最短距離をまとめたvector
//全ての辺からの距離を求めたい場合は、
//
/*
vector<vector<int> >vecを用意
↓ ↓ ↓
REP(i,V_){
DIJKSTRA.shortest(i);
vec.push_back(DIJKSTRA.dist);
}
DIJKSTRA.init();
これはO(N*N*log2(N))
*/
vector<vector<edge> > G;
//頂点a,bが両方向に繋がってるなら、
//Gには(a,b)と(b,a)の場合の両方を入れないといけない
/*
REP(i ,G.size()){
while(頂点iに繋がってる辺の個数){
G[i].push_back(辺の情報edge);
}
}
*/
dijkstra(ll V_ ):G(V_){
REP(i,V_){
dist.push_back(INF);
}
V=V_;
}
~dijkstra(){
std::vector<ll>().swap(dist);
vector<std::vector<edge> >().swap(G);
}
void init(){
REP(i,dist.size())dist[i] = INF;
}
void shortest(int s) {
priority_queue<pll, vector<pll>, greater<pll> > que;
dist[s] = 0;
que.push(pll(0, s));
while (!que.empty()) {
pll p = que.top();
que.pop();
int v = p.second;
if (dist[v] < p.first) continue;
for (int i=0; i<G[v].size(); ++i) {
edge e = G[v][i];
if (dist[e.to] > dist[v] + e.cost) {
//dist[e.to] == dist[v] + e.costを含めたらダメ、無限更新ループするから
dist[e.to] = dist[v] + e.cost;
que.push(pll(dist[e.to], e.to));
}
}
}
}
};
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////
//----UnionFind-----
//----UnionFind-----
class UnionFind{
public:
int* par;
int Size;
vll rank;//rankが高いほど上の親である
//配列の中身は0 ~ N-1
UnionFind( LL N):rank(N){
Size = N;
par = new int[N];
REP(i,Size)par[i] = i;
REP(i,N)rank[i] = 0;
}
~UnionFind(){
Release();
}
void Release()
{
if (par == NULL) {
return;
}
delete[] par;
par = NULL;
}
void init(){
par = new int[Size];
REP(i,Size)par[i] = i;
}
LL root(LL x){
if(par[x] ==x)return x;
else {
par[x] = root(par[x]);
return par[x];
}
}
void unite(LL x, LL y){
LL rx = root(x);
LL ry = root(y);
if(rx == ry)return;
if(rank[rx] < rank[ry]){
par[rx] = ry;//rankの高い方を親にする
}else{
par[ry] = rx;
if(rank[rx] == rank[ry]){
//rankがどちらも同じ時、どちらか好きな方を親にしてそのrankを1上げる
rank[rx]++;
}
}
}
bool same(LL x, LL y){
LL rx = root(x);
LL ry = root(y);
return rx == ry;
}
};
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////
//--------BFS---------
class BFS{
public:
BFS(vector<vector <char> > field_){
field = field_;
h=field.size();
w=field[h-1].size();
initial_number = INF;
REP(i,h){
dist.push_back(vector <LL> (w , initial_number));
}
}
~BFS(){
std::vector<std::vector<ll> >().swap(dist);
std::vector<std::vector<char> >().swap(field);
}
vector<vector <char> > field;
ll h;
ll w;
ll initial_number;//初期化用数値
vector< vector<LL> >dist; //この変数に書き込む
pair<LL , LL > plus(pair<LL , LL> &a, pair<LL , LL > &b){
pair<LL , LL> p;
p.first = a.first + b.first;
p.second = a.second + b.second;
return p;
}
bool equal(pair<LL , LL> &a, pair<LL , LL > &b){
return (a.first == b.first && a.second == b.second);
}
bool is_in_field(int h, int w, const pair<LL , LL> &point)
{
const int c = point.second;
const int r = point.first;
return (0 <= c && c < w) && (0 <= r && r < h);
}
// fieldの中身を初期化
void init(){
REP(i,dist.size()){
REP(t,dist[i].size()){
dist[i][t] = initial_number;
}
}
}
// sy , sx はスタート位置の 『INDEX』!!
// syが縦 sx が横
// .を道、#を障害物とする
void shortest(ll sy,ll sx){
//初期化
init();
pair <LL , LL> c[4];
c[0].first = 0;
c[0].second = 1;
c[1].first = 0;
c[1].second = -1;
c[2].first = 1;
c[2].second = 0;
c[3].first = -1;
c[3].second = 0;
queue <pair<LL ,LL> >Q;
pair<LL , LL> s;
s.first = sy;
s.second = sx;
dist[sy][sx] = 0;//スタート位置のみ0で初期化
Q.push(s);
while(Q.empty() == false){
//sを根とした木を考える
//グリッド上で隣り合っている頂点間には辺があると考えると、
//sから頂点（節点）への最短距離は考えたい頂点(節点)の高さ（深さ）である。
//木の高さxの頂点を全て調べ終えてから高さx+1の頂点を調べていくので,
//最初に到達した時点での距離が最短距離である。
pair <LL , LL> now = Q.front();
Q.pop();
for(int u = 0; u < 4 ; u++){
pair<LL , LL > x = c[u];
pair<LL , LL> next = plus(now , x);
if(is_in_field(h,w,next)){
if(field[next.first][next.second] == '.'){
//更新
if(dist[next.first][next.second] > dist[now.first][now.second] + 1){
//dist[next.first][next.second] == dist[now.first][now.second]+1を含めたら無限更新ループするからダメ
//初到達時が最小値なのでdist[next.first][next.second]==initial_numberでも良いが、
//01BFSの時に > を使う必要があるのでこうする
dist[next.first][next.second] = dist[now.first][now.second] + 1;
//distの値を更新し、次の頂点をqueueに追加する
Q.push(next);
}else{
//すでに到達済みである＝＝これ以前にQueueから出てきたpairがすでに
//到達している＝＝すでにdistの値が最小値である;
//到達済みの頂点は既に一度queueに追加されているため、追加する必要はない
//
}
}
}
}
}
}
};
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//------------文字列ソート-------------
void StringSort(vector<string> &S){
map<int , int> SwapInd;
int maxi = 0;//Sに含まれる文字列の最大文字列長
for(int i = 0 ; i < S.size() ; i++){
if(S[i].size() > maxi) maxi = S[i].size();
}
for(int i = 0 ; i < maxi ; i++){//ここが右端の文字から左の文字へのループ
//やりたいこと:Sの要素で、右からi文字目でソートするものを右側に,しないものを左側に持ってくる
int k = maxi - i;//今考えている文字が左から何文字目かを表す(indexではないので-1することに注意)
int sort_num = 0;//文字列長がk以上ある要素の個数
//ソートしたい文字列の個数と言い換えられる
for(int j = 0 ; j < S.size() ; j++){
if(S[j].size() >= k){//S[j]にk文字目が存在すればSwapInd[j]に記録
SwapInd[j]=1;
sort_num++;//インクリメント
}
}
int swapped = 0;//Sの右側グループの左端indexを0としたきのindex
//ここからグループ分けをします
for(int j = 0 ; j< S.size() ; j++){
//ここで、S.size() - sort_num は右側と左側の境界である
if(SwapInd[j] == 1 && j < S.size() - sort_num){
//j番目の文字列がソート対象（文字列長k以上）
//かつ、S[j]が右側グループに入っていない
if(SwapInd[S.size() - sort_num + swapped] == 0){
//右側グループの左からswapped番目の文字列がソート対象でない場合
iter_swap(S.begin() + j , S.begin() + S.size() - sort_num + swapped);
//入れ替える
}else{
//右側グループの左からswapped番目の文字列がソート対象である場合
//右側グループの左からswapped番目の文字列がソート対象でなくなるまで
//swappedをインクリメントする
while(SwapInd[S.size() - sort_num + swapped] != 0){
swapped++;
if(S.size() - sort_num + swapped >= S.size()){
break;//out of index
}
if(S.size() - sort_num + swapped < S.size()){
iter_swap(S.begin() + j , S.begin() + S.size() - sort_num + swapped);
}
}
}
SwapInd[j] = 0;//更新
SwapInd[S.size() - sort_num + swapped] = 0;//更新
swapped++;//左右境界から何番目に要素を追加するかを表す
}//Sのグループ分け完了
}
vector<string> WhatSorted(sort_num);
vector<pair<int , int> > char_and_index(sort_num);
//sortする文字とそのindex,
for(int j = 0 ; j < sort_num ; j++){
//(int)charの値は大文字小文字で異なるので、char_and_indexでは仮想的に全て統一する
//S や WhatSorted内では大文字小文字を統一しないで良い
if(S[S.size() - sort_num + j][k-1] >= 65 &&S[S.size() - sort_num + j][k-1] <=90){
char_and_index[j].first = (int)S[S.size() - sort_num + j][k-1] + 32;
}else{
char_and_index[j].first = (int)S[S.size() - sort_num + j][k-1];
}
char_and_index[j].second = j;
WhatSorted[j] = S[S.size() - sort_num + j];//境界からj番目の文字列
}
//マージソートなので同じ値同士の順番は保持
stable_sort(char_and_index.begin() , char_and_index.end());
for(int j = 0 ; j < sort_num ; j++){
S[S.size() - sort_num + j] = WhatSorted[char_and_index[j].second];
//WhatSortedの中身はk+1文字目以降で既にソートしてあるので、
//k番目の文字が同じ場合の順番を保持しつつ、
//k番目の文字ででソートすればk文字目以降でソートされた状態になる
//つまり、char_and_indexにk文字目を入れ、それを文字が同じ場合の順番を保持しつつソートし、
//char_and_indexでソートされた順番でWhatSortedから取り出せば良い
}
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//---------------------------ダブリング----------------------------
struct Doubling{
public:
ll n;
ll k;
//n以下の周期でループしているとする
//next[j][i] := i番目の要素の2^j個先の要素
//next[k][n]
Doubling(ll n_ ){
n = n_;
k = 100;
next.resize(k , vll(n , -1));
}
~Doubling(){}
vector<vll> next;
void init(){
k = 100;
next.resize(k , vll(n , -1));
}
void calc(){
//next[0][i]の中身は自分で書き換えます
REP(j,k-1){
REP(i,n){
if(next[j][i] == -1){
//値がない場合
next[j+1][i] = -1;
}else{
if(next[j][i]>=n)next[j+1][i] = -1;
//a[i]の2^(j+1)個先はi番目の要素の2^j個先のさらに2^j個先
else next[j+1][i] = next[j][next[j][i]];
}
}
}
}
};
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//int(S)以下の整数のうちベクトルxの要素（0~9）のどれかが少なくとも1度はどこかの桁に現れるような整数の個数
ll ketaDP(string Snum , vector<ll> x){
ll ans = 0;
//桁DPにおけるdp[i][0][0]をnow00に対応させる
//dp[i][smaller][judje] の i はindex,
//smallerは考える値が左からi+1桁までで最大値になるかどうか
//judgeは条件を満たしているかどうか
ll now00 , now01 , now10 , now11;
ll next00 , next01 , next10 , next11;
vector<ll> SmallNum(11,0); // SmallNum[i]は ベクトルxのなかにi未満の数がいくつあるか
mll px; // px[i] : iがベクトルxに含まれるかどうか
ll xSize = 0;///x内にある要素の種類の数(被りのない数)
now00 = 1;//最初は左から0桁目であり、左から0桁までの最大値かつ条件を満たさない場合である
now01 = 0;
now10 = 0;
now11 = 0;
REP(i,x.size())px[x[i]]++;
REP(i,11){
if(px[i]!=0)xSize++;
if(i==0){
if(px[i]!=0)SmallNum[i+1]++;
}else if(i < 10){
SmallNum[i] += SmallNum[i-1];
if(px[i]!=0)SmallNum[i+1]++;
}else if(i==10){
SmallNum[i] += SmallNum[i-1];
}
}
REP(i,Snum.size()){
next00 = now00*(px[Snum[i]-48]==0);
next01 = now00*(px[Snum[i]-48]!=0) + now01;
next10 = now10*(10-xSize) + now00*(Snum[i]-48 - SmallNum[Snum[i]-48]);
next11 = now11*10 + now10*xSize + now01*(Snum[i]-48)+now00*SmallNum[Snum[i]-48];
now00 = next00;
now01 = next01;
now10 = next10;
now11 = next11;
}
ans = now01 + now11;
return ans;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//MODの計算
//MODの計算
//MODの計算
//MODの計算
long long modpow(long long a, long long n, long long mod) {
long long res = 1;
while (n > 0) {
if (n & 1) res = res * a % mod;
a = a * a % mod;
n >>= 1;
}
return res;
}
long long modinv(long long a, long long m) {
long long b = m, u = 1, v = 0;
while (b) {
long long t = a / b;
a -= t * b; swap(a, b);
u -= t * v; swap(u, v);
}
u %= m;
if (u < 0) u += m;
return u;
}
ll moddiv(ll a , ll b , ll m){
a%=m;
return a*modinv(b,m)%m;
}
// a^x ≡ b (mod. m) となる最小の正の整数 x を求める
long long modlog(long long a, long long b, long long m) {
a %= m, b %= m;
// calc sqrt{M}
long long lo = -1, hi = m;
while (hi - lo > 1) {
long long mid = (lo + hi) / 2;
if (mid * mid >= m) hi = mid;
else lo = mid;
}
long long sqrtM = hi;
// {a^0, a^1, a^2, ..., a^sqrt(m)}
map<long long, long long> apow;
long long amari = a;
for (long long r = 1; r < sqrtM; ++r) {
if (!apow.count(amari)) apow[amari] = r;
(amari *= a) %= m;
}
// check each A^p
long long A = modpow(modinv(a, m), sqrtM, m);
amari = b;
for (long long q = 0; q < sqrtM; ++q) {
if (amari == 1 && q > 0) return q * sqrtM;
else if (apow.count(amari)) return q * sqrtM + apow[amari];
(amari *= A) %= m;
}
// no solutions
return -1;
}
//nが大きい場合用のmodcomb
//nが大きい場合用のmodcomb
//Modが素数の場合が安全
//Modが素数の場合が安全
//計算量はO(r)
//計算量はO(r)
ll modcomb(ll n , ll r , ll Mod){
ll N = 1;
ll K = 1;
REP(i,r){
N*=(n-i)%Mod;
K*=(i+1)%Mod;
N%= Mod;
K%= Mod;
}
return (N*modinv(K,Mod))%Mod;
//modinvはKの逆元を求めている
//modinvの別解:
//Modが素数の時、Y^(Mod-1) = Y*(Y^Mod-2) = 1 (mod Mod)
//よってY^(Mod-2) = Y^(-1) = 1/Y (mod Mod)
//よって nCk = {n*(n-1)* ... *(n-k+1)} / (k!)
//は nPk * (k!)^(-1) = nPk * modpow(k! , Mod-2 , Mod)である
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//-----------MODつきCombination------------//
class ModComb{
//これは何度も計算で使う場合用、MAXが小さい時(10000000とか)じゃないとダメ
//これは何度も計算で使う場合用、MAXが小さい時(10000000とか)じゃないとダメ
//これは何度も計算で使う場合用、MAXが小さい時(10000000とか)じゃないとダメ
public:
vll fac ;
vll finv ;
vll inv ;
ModComb(ll MAX_ , ll MOD_):fac(MAX_),finv(MAX_),inv(MAX_){
MAX = MAX_;
MOD = MOD_;
}
~ModComb(){
std::vector<ll>().swap(fac);
std::vector<ll>().swap(finv);
std::vector<ll>().swap(inv);
}
int MAX;
int MOD;
// テーブルを作る前処理
void COMinit() {
fac[0] = fac[1] = 1;
finv[0] = finv[1] = 1;
inv[1] = 1;
for (int i = 2; i < MAX; i++){
fac[i] = fac[i - 1] * i % MOD;
inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
finv[i] = finv[i - 1] * inv[i] % MOD;
}
}
// 二項係数計算
long long COM(int n, int k){
if (n < k) return 0;
if (n < 0 || k < 0) return 0;
return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
};
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//-------------bit全探索---------------
//aは空の二重配列
//aに格納する
//a[i]には小さい方からi個目の,n桁のbinaryで1が現れる桁の情報が入っている
//a[i][j]はa[i]のbitが1になる桁を表す。
//a[i]について、0 <= i <= 2^n - 1;
//a.size() == 2^n
void BIT(vector<vll> &a , ll n){
for(ll bit = 0; bit < (1<<n) ; bit++){
vll P;
a.push_back(P);
for(ll i = 0 ; i < n ; i++){
if(bit & (1<<i)){
a[bit].push_back(i);
}
}
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//桁数
int getdigit(ll n){
return log10(n)+1;
}
ll keta(ll n , ll k){//k番目の桁を返す (k >= 1)//O(n)なので要改善
if(k > getdigit(n)){
return -1;
}else if(k==1){
return n%10;
}else{
ll p = 1;
REP(i,k)p*=10;
return (n%p)/(p/10);
}
}
ll kiriage(ll a , ll b){
return a/b + 1;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//-------素因数分解---------------
//first に素因数 , secondに個数
vector<pair<ll , ll > > PrimeFactors(ll n)
{
std::map<ll,ll> out;
vector<pair<ll , ll > > answer;
while (n % 2 == 0)
{
++out[2];
n = n / 2;
}
if(out[2])answer.push_back(make_pair(2 , out[2]));
for (ll i = 3; i <= sqrt(n); i = i + 2)
{
while (n%i == 0)
{
++out[i];
n = n / i;
}
if(out[i])answer.push_back(make_pair(i , out[i]));
}
if (n > 2)
++out[n];
if(out[n])answer.push_back(make_pair(n , out[n]));
return answer;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
class Matrix{
//vector : matの書き換え
//mat は長方形でないといけない
public:
Matrix(vector<vector<long long> > &mat_){
mat = mat_;
}
~Matrix(){
mat.resize(0);//resizeではO(n^2)かかるのでは？
}
vector<vector<long long> > mat;
void trans(){
int y_size = mat.size();
int x_size;
if(y_size == 0){
x_size = 0;
}else{
x_size = mat[0].size();
}
vector<vector<long long > > cop(x_size , vector<long long>(y_size));
for(int i = 0 ; i < y_size;i++){
for(int j = 0 ; j < x_size ; j++){
cop[j][i] = mat[i][j];
}
}
mat.resize(x_size);
//for(int j = 0 ; j < x_size ; j++)mat[j].resize(y_size);
copy(cop.begin() , cop.end() , mat.begin());
}
void x_reverse(){
for(int i = 0 ; i < mat.size() ; i++){
reverse(mat[i].begin() , mat[i].end());
}
}
void y_reverse(){
reverse(mat.begin() , mat.end());
}
void Debug(){
for(int i = 0 ; i < mat.size();i++){
for(int j = 0 ; j < mat[i].size();j++){
cerr << mat[i][j] << " " ;
}
cerr << endl;
}
}
};
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//-----------配列の要素の連続部分をまとめる---------
//xの連続してる部分をvectorにまとめる , firstが連続する領域の大きさ、secondが領域を構成する値
template<class T>//Tはvector or string
vector<pll> sequence(T x){//xの連続してる部分をvectorにまとめる
// firstが連続する個数、secondが値
//xのうち,同じ値が隣り合っているような領域の大きさをfirstにいれる
//ex. {1,1,1,1,4,3,3,3,5,5,2,2} -> {4,1,3,2,2}
// second には,i番目の領域がどの値で構成される領域かをいれる
//ex. {1,1,1,1,4,3,3,3,5,5,2,2} -> {1,4,3,5,2}
//xがstringの場合, 文字を整数にcastしてsecondにいれる
vector<pll> s;
bool flag = 0;//今連続しているかどうか
ll now;
ll seq = 1;
ll next;
REP(i,x.size()){
if(i+1 >= x.size()){//次の数が範囲外になるとき
now = (ll)x[i];
s.push_back(MP(seq , now));
break;
}else{
now = x[i];
next = x[i+1];
if(flag){
if(now == next){
seq++;
}else{
s.push_back(MP(seq , now));
seq = 1;
flag = 0;
}
}else{
if(now == next){
seq++;
flag = 1;
}else{
s.push_back(MP(seq , now));
seq = 1;
}
}
}
}
return s;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// グラフ、頂点の入次数、頂点数を受け取り、そのトポロジカルソートを記録した配列を返す関数
vector<int> topological_sort(vector<vector<int> > &G, vector<int> &indegree, int V) {
// トポロジカルソートを記録する配列
vector<int> sorted_vertices;
// 入次数が0の頂点を発見したら、処理待ち頂点としてキューに追加する
queue<int> que;
for (int i = 0; i < V; i++) {
if (indegree[i] == 0) {
que.push(i);
}
}
// キューが空になるまで、操作1~3を繰り返す
while (que.empty() == false) {
// キューの先頭の頂点を取り出す
int v = que.front();
que.pop();
// その頂点と隣接している頂点の入次数を減らし、0になればキューに追加
for (int i = 0; i < G[v].size(); i++) {
int u = G[v][i];
indegree[u] -= 1;
if (indegree[u] == 0) que.push(u);
}
// 頂点vを配列の末尾に追加する
sorted_vertices.push_back(v);
}
// トポロジカルソートを返す
return sorted_vertices;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//パスカルの三角形
vector<vector<ll> > pascal(66);//65段までならいける
vll getpascal(ll n){
if(pascal[n].size()>0)return pascal[n];
vll e;
if(n == 0){
e.push_back(1);
}else{
e.push_back(1);
vll ajj = getpascal(n-1);
for(int i = 0 ; i < ajj.size()-1 ; i++){
e.push_back(ajj[i]+ajj[i+1]);
}
e.push_back(1);
}
return pascal[n] = e;
}
void pascalCalc(ll n){
pascal[n] = getpascal(n);
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//セグメントツリー
// vector<int>を渡してあげると、それを元にセグメント木を構築する。
class SegmentTree {
ll n; // 最下段のノード数
vector<ll> node;
ll SIJK; // 最弱なやつ(INFとか-1とか)
public:
//コンストラクタにはvectorをいれる
SegmentTree(vector<ll> v) {
SIJK = INF;
ll sz = v.size();
n = 1;
while (n < sz) n *= 2; // n…最下段の横幅
node.resize(2 * n - 1, SIJK);
// 最下段に突っ込む
for (int i = 0; i < sz; i++) node[(n - 1) + i] = v[i];
// 最下段以外を更新していく
for (int i = n - 2; i >= 0; i--) {
node[i] = compare(node[i * 2 + 1], node[i * 2 + 2]);
}
}
// 結合法則を満たすやつならなんでもいいよー。aかbを返す。
ll compare(ll a, ll b) {
return min(a, b);
}
// 配列でi番目の要素をvalに変更する
void update(ll i, ll val) {
// まず最下段(2n-1)を変更する
i += n - 1;
node[i] = val;
// 上に行きながら更新していく
while (i > 0) {
i = (i - 1) / 2; // 親へ
node[i] = compare(node[2 * i + 1], node[2 * i + 2]);
}
}
ll getval(ll i){
return node[i+n-1];
}
// [a,b) 中の結果を返す。[l,r)は対称区間の左端と右端。
// サイズがnのとき、0<= a,b <= n
ll get(int a, int b, int now = 0, int l = 0, int r = -1) {
// 初期化
if (r < 0) r = n;
// 俺は関係ないとき -> 答えの邪魔にならない値を返す
if (r <= a || b <= l) return SIJK;
// 要求区間の中にノードがすっぽり入ってる → 計算候補として返す
if (a <= l && r <= b) return node[now];
// ノードの一部分だけ要求区間に入ってる → 子を再帰的に探索する
ll vl = get(a, b, 2 * now + 1, l, (l + r) / 2); // 子(左)
ll vr = get(a, b, 2 * now + 2, (l + r) / 2, r); // 子(右)
return compare(vl, vr);
}
};
//地縁セグ
struct LazySegmentTree {
private:
int n;
vector<ll> node, lazy;
public:
//コンストラクタにはvectorをいれる
LazySegmentTree(vector<ll> v) {
int sz = (int)v.size();
n = 1; while(n < sz) n *= 2;
node.resize(2*n-1);
lazy.resize(2*n-1, 0);
for(int i=0; i<sz; i++) node[i+n-1] = v[i];
for(int i=n-2; i>=0; i--) node[i] = node[i*2+1] + node[i*2+2];
}
void eval(int k, int l, int r) {
// 遅延配列が空でない場合、自ノード及び子ノードへの
// 値の伝播が起こる
if(lazy[k] != 0) {
node[k] += lazy[k];
// 最下段かどうかのチェックをしよう
// 子ノードは親ノードの 1/2 の範囲であるため、
// 伝播させるときは半分にする
if(r - l > 1) {
lazy[2*k+1] += lazy[k] / 2;
lazy[2*k+2] += lazy[k] / 2;
}
// 伝播が終わったので、自ノードの遅延配列を空にする
lazy[k] = 0;
}
}
void add(int a, int b, ll x, int k=0, int l=0, int r=-1) {//区間に+xする
if(r < 0) r = n;
// k 番目のノードに対して遅延評価を行う
eval(k, l, r);
// 範囲外なら何もしない
if(b <= l || r <= a) return;
// 完全に被覆しているならば、遅延配列に値を入れた後に評価
if(a <= l && r <= b) {
lazy[k] += (r - l) * x;
eval(k, l, r);
}
// そうでないならば、子ノードの値を再帰的に計算して、
// 計算済みの値をもらってくる
else {
add(a, b, x, 2*k+1, l, (l+r)/2);
add(a, b, x, 2*k+2, (l+r)/2, r);
node[k] = node[2*k+1] + node[2*k+2];
}
}
//区間の値を取得する前に絶対ここをチェック！！-----------------------------------
ll compare(ll a , ll b){//演算を指定する
//どれか + , min , max
return max(a,b);
//return min(a,b);
//return max(a,b);
}
ll query(int a, int b, int k=0, int l=0, int r=-1) {//compareで指定された演算を区間に適用する
if(r < 0) r = n;
if(b <= l || r <= a) return 0;
// 関数が呼び出されたら評価！
eval(k, l, r);
if(a <= l && r <= b) return node[k];
ll vl = query(a, b, 2*k+1, l, (l+r)/2);
ll vr = query(a, b, 2*k+2, (l+r)/2, r);
return compare(vl,vr);
}
ll getval(ll i){//配列のi番目の要素の値を取得
return query(i , i + 1);//区間の長さが1なら、演算に関係なくその区間のノードの値を返す。
}
};
//区間の値を同じ値にする
struct RMQ1 {
int n;
vector<ll> dat, lazy;
// 要素数を入れる
RMQ1(int n_) : n(), dat(n_ * 4, INF), lazy(n_ * 4, INF) {
int x = 1;
while (n_ > x) x *= 2;
n = x;
}
/* lazy eval */
void eval(int k) {
if (lazy[k] == INF) return; // 更新するものが無ければ終了
if (k < n - 1) { // 葉でなければ子に伝搬
lazy[k * 2 + 1] = lazy[k];
lazy[k * 2 + 2] = lazy[k];
}
// 自身を更新
dat[k] = lazy[k];
lazy[k] = INF;
}
ll compare(ll a , ll b){//queryの取得する値の種類を帰る場合、ここを変更する
return min(a,b);
}
void update(int a, int b, ll x, int k, int l, int r) {
eval(k);
if (a <= l && r <= b) { // 完全に内側の時
lazy[k] = x;
eval(k);
} else if (a < r && l < b) { // 一部区間が被る時
update(a, b, x, k * 2 + 1, l, (l + r) / 2); // 左の子
update(a, b, x, k * 2 + 2, (l + r) / 2, r); // 右の子
dat[k] = compare(dat[k * 2 + 1], dat[k * 2 + 2]);
}
}
void update(int a, int b, ll x) { update(a, b, x, 0, 0, n); }
ll query_sub(int a, int b, int k, int l, int r) {
eval(k);
if (r <= a || b <= l) { // 完全に外側の時
return INF;
} else if (a <= l && r <= b) { // 完全に内側の時
return dat[k];
} else { // 一部区間が被る時
ll vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
ll vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
return compare(vl, vr);
}
}
ll query(int a, int b) { return query_sub(a, b, 0, 0, n); }
/* debug */
inline ll operator[](int a) { return query(a, a + 1); }
void print() {
for (int i = 0; i < 2 * n - 1; ++i) {
cout << (*this)[i];
if (i != n) cout << ",";
}
cout << endl;
}
};
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// toBinary[i]は,binaを二進数で表したときの下からi桁目のbitが入ってる
vll toBinary(ll bina){
vll ans;
for (ll i = 0; bina>0 ; i++)
{
ans.push_back(bina%2);
bina = bina/2;
}
return ans;
}
//-----------MAIN------------//
//注意::::DPの配列、vectorはグローバル変数を使え！！そして引数として与えるな！！
// sqrは２乗 sqrtはルート
// 関数の引数にサイズのでかいvectorを与えるとTLEの恐れあり（不確定）
// サイズのでかいvectorに関数内でアクセスしたいときはグローバル変数を使おう
int main(){
ll n , m ;
map<ll , ll>p;
ll h , w , k;
ll y;
string s;
long double mm;
cin >> n >> k;
cin >> s;
ll syu = k+1;
ll lim = n-2;
ll was = n;
ll fl = (n-1)%(k+1) ;
REP(i,s.size()){
ll now = n-1-i-1;
ll limit = n-1-i-1;
if((now+1)%(k+1) == fl || (now+1<=k && was - (now+1) >= k+1) ){
//debug(now+1)debug(fl)
if(s[now]!='x'){
}else{
while(now-1>=0 && s[now]=='x'){
now--;
i++;
}
}
//debug(now+1)
was = now+1;
fl = (was)%(k+1);
if(now+1 <= k){
if(s[now]!='x'){
}else{
while(now>=0 && s[now]=='x'){
now--;
i++;
}
}
if(now<0){
cout << 0 << endl;
}
else cout << now+1<<endl;
return 0;
}
}
}
cout << 0 << endl;
return 0;
}