QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#447398#3149. TerritoryJohnAlfnov100 ✓111ms39728kbC++142.9kb2024-06-18 13:09:292024-06-18 13:09:29

Judging History

This is the latest submission verdict.

  • [2024-06-18 13:09:29]
  • Judged
  • Verdict: 100
  • Time: 111ms
  • Memory: 39728kb
  • [2024-06-18 13:09:29]
  • Submitted

answer

#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
#define gmap __gnu_pbds::cc_hash_table
char s[100005];
int X[100005],Y[100005];
#define M 1000000
inline long long mk(int x,int y){
	return 1ll*(x+M)*M+y;
}
void output(vector<int>v){
	puts("###");
	for(auto cu:v)printf("%d ",cu);
	printf("\n");
}
vector<int>g[200005];
vector<pair<int,int>>vc[200005];
int sz[200005];
int main(){
	int n,k;
	scanf("%d%d",&n,&k);
	scanf("%s",s+1);
	X[0]=Y[0]=0;
	for(int i=1;i<=n;++i){
		X[i]=X[i-1],Y[i]=Y[i-1];
		if(s[i]=='N')++Y[i];
		if(s[i]=='S')--Y[i];
		if(s[i]=='E')++X[i];
		if(s[i]=='W')--X[i];
	}
	int rx=X[n],ry=Y[n];
	if(rx<0){
		rx=-rx;
		for(int i=0;i<=n;++i)X[i]*=-1;
	}
	if(ry<0){
		ry=-ry;
		for(int i=0;i<=n;++i)Y[i]*=-1;
	}
	int mnx=1e9,mny=1e9;
	for(int i=0;i<=n;++i)mnx=min(mnx,X[i]),mny=min(mny,Y[i]);
	for(int i=0;i<=n;++i)X[i]-=mnx,Y[i]-=mny;
	if((rx==0&&ry==0)||(k==1)){
		gmap<long long,int>mp;
		for(int i=0;i<=n;++i)mp[1ll*X[i]*(n+1)+Y[i]]=1;
		int ans=0;
		auto mpp=mp;
		for(auto pi:mpp){
			int x=pi.first/(n+1),y=pi.first%(n+1);
			if(mp[1ll*(x+1)*(n+1)+y]&&mp[1ll*(x+1)*(n+1)+(y+1)]){
				if(mp[1ll*x*(n+1)+(y+1)])++ans;
			}
		}
		printf("%d\n",ans);
		return 0;
	}
	if(rx>ry){
		swap(rx,ry);
		for(int i=0;i<=n;++i)swap(X[i],Y[i]);
	}
	map<long long,int>mp;
	int tt=0;
	for(int i=0;i<=n;++i){
		int gy=Y[i]/ry,my=Y[i]%ry;
		int mx=X[i]-gy*rx;
		long long wz=mk(mx,my);
		if(!mp[wz])mp[wz]=++tt;
		g[mp[wz]].emplace_back(gy+1);
	}
	auto pm=mp;
	for(int i=0;i<=n;++i){
		int gy=Y[i]/ry,my=Y[i]%ry;
		int mx=X[i]-gy*rx;
		if(!my){
			long long zw=mk(mx+rx,my+ry);
			if(!mp[zw])mp[zw]=++tt;
			g[mp[zw]].emplace_back(gy);
		}
	}
	for(int i=1;i<=tt;++i){
		sort(g[i].begin(),g[i].end());
		g[i].resize(unique(g[i].begin(),g[i].end())-g[i].begin());
		sz[i]=g[i].size();
		int L=0,R=0;
		for(int j=0;j<sz[i];++j){
			if(j==0||g[i][j]+1>R){
				if(j)vc[i].emplace_back(L,R);
				L=g[i][j]+1,R=g[i][j]+k;
			}else{
				R=g[i][j]+k;
			}
		}
		vc[i].emplace_back(L,R);
	}
	long long ans=0;
	for(auto pi:pm){
		int x=pi.first/M-M,y=pi.first%M;
		long long wa=mk(x,y),wb=mk(x+1,y);
		long long wc=mk(x,y+1),wd=mk(x+1,y+1);
		if(mp.find(wa)==mp.end())continue;
		if(mp.find(wb)==mp.end())continue;
		if(mp.find(wc)==mp.end())continue;
		if(mp.find(wd)==mp.end())continue;
		int A=mp[wa],B=mp[wb],C=mp[wc],D=mp[wd];
		int sa=vc[A].size(),sb=vc[B].size(),sc=vc[C].size(),sd=vc[D].size();
		int za=0,zb=0,zc=0,zd=0;
		while(za<sa&&zb<sb&&zc<sc&&zd<sd){
			int la=vc[A][za].first,ra=vc[A][za].second;
			int lb=vc[B][zb].first,rb=vc[B][zb].second;
			int lc=vc[C][zc].first,rc=vc[C][zc].second;
			int ld=vc[D][zd].first,rd=vc[D][zd].second;
			int l=max(max(la,lb),max(lc,ld));
			int r=min(min(ra,rb),min(rc,rd));
			ans+=max(0,r-l+1);
			if(ra==r)++za;
			else if(rb==r)++zb;
			else if(rc==r)++zc;
			else ++zd;
		}
	}
	printf("%lld\n",ans);
	return 0;
}

详细

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 2ms
memory: 13188kb

input:

5 1
SSWEN

output:

0

result:

ok single line: '0'

Test #2:

score: 5
Accepted
time: 2ms
memory: 13232kb

input:

8 1
NNSSENWS

output:

1

result:

ok single line: '1'

Test #3:

score: 5
Accepted
time: 2ms
memory: 13204kb

input:

15 1
ENNEEWWWWWSSNEW

output:

1

result:

ok single line: '1'

Test #4:

score: 5
Accepted
time: 2ms
memory: 13184kb

input:

25 1
NNNSEENNSESNWESEWWENWENNE

output:

2

result:

ok single line: '2'

Test #5:

score: 5
Accepted
time: 0ms
memory: 13192kb

input:

40 1
WSESWSSWENNSNEENNWEWNNEESESSSEENEWWSSNSE

output:

7

result:

ok single line: '7'

Test #6:

score: 5
Accepted
time: 0ms
memory: 13208kb

input:

45 1
SNWNEESSWSESWEEWESNEEWSWNWNNSSSEEEWNSNSNEWNSW

output:

8

result:

ok single line: '8'

Test #7:

score: 5
Accepted
time: 5ms
memory: 13180kb

input:

49 1
WEWWNNWSSWENSWENSNSSNENSENEEENSNSSEENNEEEWESWEESW

output:

6

result:

ok single line: '6'

Test #8:

score: 5
Accepted
time: 2ms
memory: 13204kb

input:

50 1
ESSWNSWNNENNSWEEEESNNWENSEEESNSEWSSEESEWWNWWSNNSWN

output:

10

result:

ok single line: '10'

Test #9:

score: 5
Accepted
time: 6ms
memory: 13192kb

input:

50 1
NNNEEESSSWWWNWSWSESSSEWSEWSSENSESSNSEWWWNNWWNENWSN

output:

9

result:

ok single line: '9'

Test #10:

score: 5
Accepted
time: 0ms
memory: 13196kb

input:

50 1
WENWWENNNWENNSSNEEWEENENSWSSESWSWWWESESNSNWSEEWSEE

output:

6

result:

ok single line: '6'

Test #11:

score: 5
Accepted
time: 0ms
memory: 13268kb

input:

50 1
WNEWENEEWWNWEESEWWENENEEEEWWEWWEWEWWSWNSWNENNEWWWE

output:

5

result:

ok single line: '5'

Test #12:

score: 5
Accepted
time: 0ms
memory: 13288kb

input:

50 1
WENSWEEWSNEWSWWNSEEWESWWSNNWNNWWENEEENWNNSSSWEWSEN

output:

9

result:

ok single line: '9'

Test #13:

score: 5
Accepted
time: 0ms
memory: 13188kb

input:

50 1
WWEESNWNSNWESSSENEWESESENWWWESNNWENSWWNEWNWNSWEESE

output:

7

result:

ok single line: '7'

Test #14:

score: 5
Accepted
time: 3ms
memory: 13192kb

input:

50 1
NENNSNSENWNWNSNSSNWWSENENWWENWSWEWEWWEWNSEWWEEWSNS

output:

7

result:

ok single line: '7'

Test #15:

score: 5
Accepted
time: 0ms
memory: 13468kb

input:

50 1
NWNWWSWSWWESNSNSSWNESWNWWESEEESEWNEWEEWSEESENNSEWN

output:

6

result:

ok single line: '6'

Test #16:

score: 5
Accepted
time: 0ms
memory: 13476kb

input:

50 1
SNENSNNSSNSSNSNSNSSNWNSNSESESSNSNNSSNSENSNNSNNNSWN

output:

7

result:

ok single line: '7'

Test #17:

score: 5
Accepted
time: 0ms
memory: 13204kb

input:

50 1
WENWNNNSSNWENNWNNWNEESNNNNSWENSSWWSNWWWSWESNWESESS

output:

6

result:

ok single line: '6'

Test #18:

score: 5
Accepted
time: 0ms
memory: 13236kb

input:

50 1
NNNNNNEEEEEESSSSSSWWWWWWNWNNNWWWSSNWSNSNWWWNSESSWE

output:

4

result:

ok single line: '4'

Test #19:

score: 5
Accepted
time: 2ms
memory: 13200kb

input:

50 1
ENEWENNWNNWEWSESWNESNNSWENEWWEWESEWNESSSENEESSSNNS

output:

5

result:

ok single line: '5'

Test #20:

score: 5
Accepted
time: 0ms
memory: 13184kb

input:

50 1
EEWWEWNWNSSNWSNSENNWSEWSENEWEESSSEEWSSWENNNWESNWWN

output:

7

result:

ok single line: '7'

Test #21:

score: 5
Accepted
time: 0ms
memory: 13488kb

input:

50 1
ENEWENSWENSWNEWNNEWWESNESNEWWESNWNSNSSNWNWWSSESWEW

output:

5

result:

ok single line: '5'

Test #22:

score: 5
Accepted
time: 0ms
memory: 13492kb

input:

49 1
NNNNNNNNNNNNEEEEEEEEEEEESSSSSSSSSSSSWWWWWWWWWWWWE

output:

0

result:

ok single line: '0'

Test #23:

score: 5
Accepted
time: 3ms
memory: 13156kb

input:

50 1
EWESSENENEWWNWWEWESWSEEWNWSWWNSSESESSEWWSENEWEEWWS

output:

8

result:

ok single line: '8'

Test #24:

score: 5
Accepted
time: 2ms
memory: 13188kb

input:

50 1
WNEWENESSNESWEWWNWNNEWWESSEWNEWWESNSENEWESWNEWSWSE

output:

7

result:

ok single line: '7'

Test #25:

score: 5
Accepted
time: 5ms
memory: 13284kb

input:

50 1
NSWSSENNSSEEENSWEWNSWWNENSSWSWSWWWNENSSEENENSWNSWE

output:

10

result:

ok single line: '10'

Subtask #2:

score: 10
Accepted

Dependency #1:

100%
Accepted

Test #26:

score: 10
Accepted
time: 0ms
memory: 13292kb

input:

350 1
NNWSEWSEWSNENNSNWSENEEWEENNSSNSEESNWNSEESSWSSSWESENSNSNNNWWNNWSSWNWENENWNNSWNSSEESNSNSESWNWSWNSSNWWWSSEEESSEESNNNEEEESWENWWWWSSWEEWENEENNSSWSWSWNNNNWNEEWEWSESNSEWWWWNWWENNWSNSNENSESNSNENSWNNEWNNEWWWESNESEEESWNNEEWNEWESNWESENNSNSNWESEWNSWWWENNEWENNNSWWENSNWENSSWENNWNSWNSSWWENSSNWWNNSNNWSNWEENSS...

output:

74

result:

ok single line: '74'

Test #27:

score: 10
Accepted
time: 0ms
memory: 13392kb

input:

5000 1
ENENWSWNSSNEWWWNNWEESSSSWWENENWSWWENNWENENWSWNSWSNWNWESWESSWWSWNNWWNESWNWEESEENNWEWNSSSEWNWSENNWENWNNSENNWENNESWSEEWSEWWNWWWESNWESEENNWNWSNENNWENSWNEWSSENESNENWWESSNWNNEESSESWWWNESSWWEESSSWWSWSSNENSESENEWESNEEEWNESSWSSSNEESNESNSWWESNNNWSWEWSNENNSNWNWSENSEESWEWNWNWWEEEEEESEEWSWEWEWNSESNSSSSWNS...

output:

916

result:

ok single line: '916'

Test #28:

score: 10
Accepted
time: 0ms
memory: 13700kb

input:

15000 1
NNSNWSWEWWWSSENWSSEWENWSWENSWEWEEWNSSSNNNNWSNNNSNNESNNWEWWSESSSNESSWSEENWWNWNSNESNNEWNWEWNSWEESSESSENENSWSNNNSEEWNESEEWSWSEWNWWWEESNENNWSSNWEENSWWSENEWEESWNWSNNNSSWNENNEWENEWWSEEWSWNNNWNWWSWNENNENEWSNWWSNSWSNWEWENNENWSESWEWWNWSNNENWSWNNWSSNEWNNSWNWSWNSSNEESESEEEEESESENSWNENSSWWENEWWSENSSESWW...

output:

2587

result:

ok single line: '2587'

Test #29:

score: 10
Accepted
time: 4ms
memory: 15124kb

input:

50000 1
WNWSNNNESSWNEWEENNNSNSENSSNNWSNWWNWWWWNEWENESESNSSWWSSWNEESENWEWWNEESSEWESSNSSWSSWENWNNWNENWSWNEWSNEEEEWWWENSSEEEEWNESWENNENNSENNSENWNENEWEWWEENEWSSEENEWEWESSESSWNESEWNNESEEWSSWSWSWSSNSEWSENESWEENSSSWEEESSNSWNWWSNSSSWSSSSESSWNWSSEESSNSENEEWNEESSEEWSNENSEWSWESEEWWNESESSSWNEESWSNNNSENENWNWNSES...

output:

9210

result:

ok single line: '9210'

Test #30:

score: 10
Accepted
time: 3ms
memory: 15124kb

input:

70000 1
ENNNSNSWSNNESWNSEWEWNWWWSNSESNNWWENSWNNWSSEESNNNENNNNNNEESNNNESSNSWNESSSENSENWNEWEWEENSWSESWNNWNNNSNNEWNNSWWEWNEWWSSNSNSSNWESNEWEEWWSWESSWSNESSNSNWSNEENEWESNNNEESNNWNSSWNSSSWSWEEESNEWSWNWNWSSESEESSEWNWEEWSSESWWWWWNSWSSNNESEWWEENNSSSWWEEEENESSNSWEEENNESNENNENNEWENNNNSSNWEWENWWNWSNENSWSWNNWWNE...

output:

11407

result:

ok single line: '11407'

Test #31:

score: 10
Accepted
time: 22ms
memory: 28528kb

input:

100000 1
NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN...

output:

3398

result:

ok single line: '3398'

Test #32:

score: 10
Accepted
time: 3ms
memory: 16124kb

input:

100000 1
NWEESSESEWSWEWSSNEWWNEESNWWWWEWWWENNSESNNWSEWSEENNSSNNSSWSNWSSSNWSNWNWNSSEEESSNNENEWWSSNWWWWWWSSNEWWSENNNNWSNSESWWWWNWWNSEEWEWNNESENNWESNSNSEWEWEESWWEEEWEENWEWSSSNEWWSSSWNWSENSSNEEWESEWSSSESWNSENEWNEEWSSNSWWESNSNNWESWWNNWNWWEWWNNENEWSNSSEWEWNENSNWSESWEENSSNNWSSSNNEESSNSSSWSWWSNWSWNNWSNNNWEN...

output:

15190

result:

ok single line: '15190'

Test #33:

score: 10
Accepted
time: 3ms
memory: 16260kb

input:

100000 1
WSSESWWNWESNNWNEENSEESESNWNSENWSNESENEWNNWENESEWNSWNNEWSNNWWWSWWNEWSNWENWNWNSSWENNEWSWNSNNWNSESEWEWWWESNNWEWNWNNESSWEESWSSSENEWNNSSEWEWNNEEEWWSENSSNESWWESSWWWNEEWNEEWNSNNNWENNENWENNSSNWSSNNESNWSWWNSSSNNNNNWSWSESSSNWWWWNNWWNENESEENNSWNSWSWSSEWWSNNWWSNNNESEEEENSSSSWWNWEEEWNENWWSEWNNNNEENWSEEE...

output:

17243

result:

ok single line: '17243'

Test #34:

score: 10
Accepted
time: 6ms
memory: 17772kb

input:

100000 1
NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN...

output:

16272

result:

ok single line: '16272'

Test #35:

score: 10
Accepted
time: 6ms
memory: 16232kb

input:

99999 1
ESNNWEWWESWWWWWEWESENNNNEEWWSSNSEESENWNNWSWNWESWSWWSENSWNNNWSNESNEESWWSNWNWWSESSSNNWWNESEWSSSNEWNNNSEENENEESWSEWSWESNNNENSENEWNNWNSESNESNENEWENSENNWWSSSWEWSSEEESESWWWSSWSWSENEEENENWEESNEWSWSWNSEEENEEWEENSEWWNWWSSSEEWWNWEEWENSWEENSNENNENWESSNSSNSWNNNNNSENNNNSWNNNSWESWWSSNESNEESSENESSENEWNNSEE...

output:

17151

result:

ok single line: '17151'

Test #36:

score: 10
Accepted
time: 8ms
memory: 16304kb

input:

100000 1
SESEEWWSNSESWWWESWSEWSSNEWWEWEWEWSWESWEWEWWWNWEWWENWNNWNENWNWWSSENWWWEEWSNSWWNWWWWEWEENSNEEEWENWEEEEEESWWWWWEEWWWNNWSWWNESNSNEWWNWWSSSEEEEWWWEWENSNSWSESENEWWWSWWENWESSWESEEWWNNNSEEENNWWWWSNWSNEESNWWSNWEENEWWSNSNWSEENENNWNSNWWSEENWNWWWWNWEWWEEWENWWSSENSNESNWWEWNWWWESWSNEWWWWEWEESWNESENNENWEN...

output:

15563

result:

ok single line: '15563'

Test #37:

score: 10
Accepted
time: 4ms
memory: 16244kb

input:

100000 1
EEENNSSNWEWEWSNNSNSSSEWSSESSEENNENSNNNESNWSNSNNWENSWESESNWESEEEWSEEEEEESWNEEWSEWNSNWSNSEWSESESESNSWSEEEEENSWSNNNEESWENSWESNENESENNWENSWWNNSEWWWEWWENSSNWSNEWWSSSWNNEEWNWSSWNEWNWNWWSEWNWWNWEWSSNWSNWSSNSNSWWNNNWNNWNNNWWSSWWNESSNSWWENEEESEENWSWNEWSSNEENENSWNEWWSSSENWSWENNWSNWNESESWWWESSNNWNNSSS...

output:

16724

result:

ok single line: '16724'

Test #38:

score: 10
Accepted
time: 4ms
memory: 16236kb

input:

100000 1
NWNENNWNWSWWESNWWSWESNNWENNWNSWSNNEWENWNNEWESEWNWWWSNSESNEENSSEWENEWSWNESNSENSEWNSESNSWWEEENEESENEWWEWSSSNSSSNSSSNWWWWNWSWSNNWSEWSNSWWNENWSNSSWSNNSSNNWWEESNENWSENNESNENWNNNSNNNENWWSSNEESNNESEENWSEEWSNNSENWNNSENEESNEEWWNEWEENNWEEEEWEESSWNSWWESEEESSESWNENENNWESWENESESENSSWNENWENENEWWEWWSENNEE...

output:

16277

result:

ok single line: '16277'

Test #39:

score: 10
Accepted
time: 6ms
memory: 16144kb

input:

100000 1
EEEEEEWESSWSEEESSWEWSSNEWNSSSNESSWEEEESEESWEWNNSSEWEWEWNESWESEWWSEENWEWSNWSNWNSWNSEWWSSWENEEWNWSWESSSWESWWNWNWSWNWENEWESNWSNWSWWWWWWSESEWNEENSESEEESSNEWNENESEWWWSWEESENEWSWSENWEWWWSNSNWESSSWWEWESSEESNSWESWWSWEEWEWWSSWSEWEEEEWEWEWEWEENNSESNSNEENSWEEEEEWWWWNNWWWWWNESNESEWEWNNWSEEENSSEWNEEEEWN...

output:

16934

result:

ok single line: '16934'

Test #40:

score: 10
Accepted
time: 0ms
memory: 16280kb

input:

100000 1
EESESWSWWWEWWSNWSEWSWWSNNWNNWSWWSWSNSSWSSNWWNWWWNSWSNWENNENWWEESWESNEEESWEWNNSWSWWWWWWEWSEENEEEEWSNNWNEWEWEEWNSWWNEWSWNWNWNWWSSWNNESWNESNWNSNSEWWNNESSWWNWENNENNNSNWSNEWWWWNESNNSNEEEWNNEWSEWWENWSESWEWENESSNSNWEENWEWWSNWNENSSWWNNSWEWSESWEEEWSSEEWEWNSENNEWSNNSWNENWSWEWSWEESNEEWSWEEWEWSNSEWWSEW...

output:

15395

result:

ok single line: '15395'

Test #41:

score: 10
Accepted
time: 7ms
memory: 16184kb

input:

100000 1
NWSSSSSSESSWENSWENNEWSNSNNWSSNSNWENNNSNENWNSSSSNSNWSSSWNSESNNSSSNENSSSNWNSSWNNNSWSSWSSNNNWNNSNNSENNWNSSSWSNNNEEWNWNNSSSSSNSWNWNNSSSENSESSNNNSNSENENNSNNNSNNSNWNNESSSSNWWWSESSNSWSSSNSSNNNNESESNNSSSSNSWNSEWNESSSWWNNSSWSNSSNSNSNENNNNSSNNNSWSENNSNSSNSENSSWSNSNNSSSSSSNSSNSSNWNSSSSWESWNWNNSNNNNNSS...

output:

14400

result:

ok single line: '14400'

Test #42:

score: 10
Accepted
time: 0ms
memory: 15464kb

input:

100000 1
ESSNNSSSNESNSSSNSNSSSNWNSSNNNNSSSSWNNNSNNSNENSNEWNNENNNNNNSNNNSSSSSSNNWSNNNSSNNNSNSWNNESSSSNSNNNENWWSNSSNSNNSSSNSSNSNSWSSSSENSNSNSNNNNENENNNESEWNWEWNSSNNSSSNSWNWNSSEWSSSNNNSSSWNESSSNESSNSSNNENSNSSNSWNSWNNNNNNNSNNNNSSSSNNSNSSNWNSSNNSENSSSSSESSENSSNSWSNWNSNWNSSSNESWNSSESNSNSNSWSNSNSNNNNENSSNW...

output:

12001

result:

ok single line: '12001'

Test #43:

score: 10
Accepted
time: 4ms
memory: 16208kb

input:

100000 1
SEWSWSNSWEENSSWWNENSSSSWSSWWNWWWESWNESWWNENWWEESWNSWNWNNSESNEEESEWSSSSEEESNSESNSSWNESWNEESNWSNWWSWSSESSWEENNWNNENWNWSESENEWWSEWNSNSWWWNEWEEWWENWEWNNWSESESWNESWWSWNWNESESESSSESNEWNWSEWWENSWNSSWNSEWSESNEEESENNSSWWEWWSSNNSWNEEEENSESSNEWNESNNWESENSWNSWWSENSESSWSWSNESSWWNSSWWWWENENSNNSENSWWEEWEW...

output:

18044

result:

ok single line: '18044'

Test #44:

score: 10
Accepted
time: 6ms
memory: 16388kb

input:

100000 1
WWNENWEENNNSSWWEESWNNWWESSWESWNNSENSWENSSSEENESENENESNESWNWNNNNSNWWNNNENWWNEWNNEWESNWWNSEWEWEESNWNWWESSSSNNWEESNSEEESSSNEENNNNWWSENNSNWWESWSEWNSNWENWNEWWWWSSWNENSEWWSENSEWNENNESWWWEWSWNSEEEWWNEWESWNWWWENSSSWESWEWESEENENWWEEEWWNESNNENENNNNWNWESWSNSENSNNESWWWWNENEWNSWSNEEWEWSEEEENESWSEWWENNSE...

output:

15979

result:

ok single line: '15979'

Test #45:

score: 10
Accepted
time: 0ms
memory: 15880kb

input:

100000 1
NNENNSNSSSNENENSSNNWSSNSSENSSSWWNNSNSNNSSWSENNWNENNNSSSNSWSENNSSNSSSESNSNNSSENNNNNNSSSSSNNSSWNNSSWWESSESNENENWSSESNNNSNNNNWWSSSSNSESNSNNWSNNSNSSWSENWNNESNWNNWEENNWNNSWENESSNNNSSSSNNNSSSEESEENNNSSNWWSSNNNNNNEWSNNNNENNSNSNSNENESNNSEEESSSSNSNNNSSSSWNNWSENSNNNWNNESWWSSNNNENNSSWSSNNSSSSENNENNSNN...

output:

13404

result:

ok single line: '13404'

Test #46:

score: 10
Accepted
time: 15ms
memory: 21296kb

input:

100000 1
EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE...

output:

0

result:

ok single line: '0'

Test #47:

score: 10
Accepted
time: 14ms
memory: 21472kb

input:

100000 1
EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE...

output:

1

result:

ok single line: '1'

Test #48:

score: 10
Accepted
time: 38ms
memory: 29200kb

input:

99999 1
NNEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE...

output:

0

result:

ok single line: '0'

Test #49:

score: 10
Accepted
time: 11ms
memory: 29084kb

input:

100000 1
ESWSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS...

output:

1

result:

ok single line: '1'

Test #50:

score: 10
Accepted
time: 17ms
memory: 29036kb

input:

100000 1
NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN...

output:

0

result:

ok single line: '0'

Subtask #3:

score: 23
Accepted

Dependency #1:

100%
Accepted

Test #51:

score: 23
Accepted
time: 5ms
memory: 13172kb

input:

35 12345
WWNSWNEWESSNNNSNENESNWNWEWWNENEESEN

output:

86412

result:

ok single line: '86412'

Test #52:

score: 23
Accepted
time: 0ms
memory: 13200kb

input:

40 999999
SNSENSEWEWSEWWNNNENESWWNSNNWSSSNSNSEEWSN

output:

9

result:

ok single line: '9'

Test #53:

score: 23
Accepted
time: 0ms
memory: 13188kb

input:

44 3141592
SEWSSEENENNWSSWEESSEENNWENSEWSNSEESNSEWSESSE

output:

28274328

result:

ok single line: '28274328'

Test #54:

score: 23
Accepted
time: 2ms
memory: 13492kb

input:

50 18
SWSNNNNSNEESNWENSWSNEEEEWWSNWNEEWSNNNWEESNNWWWWWNE

output:

199

result:

ok single line: '199'

Test #55:

score: 23
Accepted
time: 0ms
memory: 13192kb

input:

50 593866
NENSWWESSWEEWWNSSWEESNWSEWEWNSNWWEWWESSEEWENWEEWNE

output:

4750928

result:

ok single line: '4750928'

Test #56:

score: 23
Accepted
time: 0ms
memory: 13432kb

input:

50 22526663
SWEEENESWNWESNWSWEENNNSWSWWWWSENNWNSENWWEWSESENWWE

output:

180213309

result:

ok single line: '180213309'

Test #57:

score: 23
Accepted
time: 5ms
memory: 13188kb

input:

50 3333
NNNNNNNNNNNNEEEEEEEEEEEESSSSSSSSSSSSWWWWWWWWWWWWNW

output:

76780

result:

ok single line: '76780'

Test #58:

score: 23
Accepted
time: 5ms
memory: 13444kb

input:

50 999999999
SNSSNENSNNESSWWSNWSESWEWNWNWNEWNNWSSSESNNNNEENWWNE

output:

14999999984

result:

ok single line: '14999999984'

Test #59:

score: 23
Accepted
time: 2ms
memory: 13192kb

input:

50 11516
ESNWNESWNSESSWESEWWEWENEWWSSWNSSWNSWNESSESEWNSEEWE

output:

80612

result:

ok single line: '80612'

Test #60:

score: 23
Accepted
time: 0ms
memory: 13180kb

input:

50 2938683
SSSSNEENWSWEWSWWWSWENNENNESEENEEESNNWSSEWWEESSWNES

output:

41141561

result:

ok single line: '41141561'

Test #61:

score: 23
Accepted
time: 0ms
memory: 13216kb

input:

50 5522259
SSWWENNNSNNSNESESNNWNWNESSWNEEWNENSSSWNSSSWENENENS

output:

55222591

result:

ok single line: '55222591'

Test #62:

score: 23
Accepted
time: 0ms
memory: 13192kb

input:

50 1000000000
NNENSNNWSNNNSNEESNNNNNSSSSSENSSSENESSNSSSSESESWNNN

output:

10999999996

result:

ok single line: '10999999996'

Test #63:

score: 23
Accepted
time: 0ms
memory: 13476kb

input:

49 1000000000
NNNNNNNNNNNNEEEEEEEEEEEESSSSSSSSSSSSWWWWWWWWWWWWN

output:

12000000132

result:

ok single line: '12000000132'

Test #64:

score: 23
Accepted
time: 2ms
memory: 13284kb

input:

50 2556790
EEWSENSNEEEEEWESNNWNESNNWEWESWEWWNWEENSESESWSNWNEW

output:

12783951

result:

ok single line: '12783951'

Test #65:

score: 23
Accepted
time: 0ms
memory: 13280kb

input:

50 17777777
EENNSSEEEENWEWESWNSSNWSWENWWENWSNNWESEWWNNSWWSEWSE

output:

10

result:

ok single line: '10'

Test #66:

score: 23
Accepted
time: 0ms
memory: 13232kb

input:

50 987623964
NWNWWSWNSWESEWEWEEEWENENWSWNNWESSSESEEWESEWWSNNWWE

output:

8888615679

result:

ok single line: '8888615679'

Test #67:

score: 23
Accepted
time: 2ms
memory: 13196kb

input:

50 22599000
NNNNNNNNEEEEEEEESSSSSSSSWWWWWWWWNEEWSSNNWEWENSWESW

output:

3

result:

ok single line: '3'

Test #68:

score: 23
Accepted
time: 2ms
memory: 13188kb

input:

50 1010101
EWSNSWNWSNESSENESEWWESNWNWENNWWNENSWNWNEEESSNNENWN

output:

16161615

result:

ok single line: '16161615'

Test #69:

score: 23
Accepted
time: 2ms
memory: 13196kb

input:

50 777777777
WWEEWSWSWEWSSENSNEEEWWENNEWWWNEEWSEWWEWNEWEWSESEWE

output:

4666666664

result:

ok single line: '4666666664'

Test #70:

score: 23
Accepted
time: 0ms
memory: 13284kb

input:

50 222843338
WSENNSNNNESWNWSSNEWESENSWWENSNEWEWWWSENWWSWNWNENSN

output:

2228433380

result:

ok single line: '2228433380'

Test #71:

score: 23
Accepted
time: 0ms
memory: 13188kb

input:

49 81958168
NNEEEEEEEEEEEEEEEEEEEEEEESSWWWWWWWWWWWWWWWWWWWWWW

output:

163916380

result:

ok single line: '163916380'

Test #72:

score: 23
Accepted
time: 0ms
memory: 13484kb

input:

48 995705840
EEEEEEEEEEENNNNNNNNNNNWESSSSSSSSSSSWWWWWWWWWWWEN

output:

10952764285

result:

ok single line: '10952764285'

Test #73:

score: 23
Accepted
time: 0ms
memory: 13196kb

input:

50 506263736
EEEEEEEEEEEEEEEEEEEEEEENSWWWWWWWWWWWWWWWWWWWWWWWNE

output:

11644065906

result:

ok single line: '11644065906'

Test #74:

score: 23
Accepted
time: 3ms
memory: 13184kb

input:

47 730672958
NNEEEEEEEEEEEEEEEEEEEEEESSWWWWWWWWWWWWWWWWWWWWW

output:

1461345958

result:

ok single line: '1461345958'

Test #75:

score: 23
Accepted
time: 0ms
memory: 13180kb

input:

50 282828282
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWES

output:

282828281

result:

ok single line: '282828281'

Subtask #4:

score: 62
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #76:

score: 62
Accepted
time: 0ms
memory: 13532kb

input:

8000 122562148
NESEEESESENEEEEEWENWENSEESEEEWWWWNWWWSNWWNEEWWENSWWSNNNWESWNEENEWWWSWESEESNWSWSWWNWNWSEEWWNEESEESEWWWESSWSENEEENNNEWWWENSSNWEWSSWENWWSSNNSWWWEWEWWEEEEESWWWNEWWESESWNENWEEWENSESSNENWWEWWWWNWWWNSNEEESNSESNSNWWWNEESWWNNEWSWENESNNNSSWESWEWWEESNSEWWWNNENENSNWENEEWEEWWWSEWWWESWWNWWWWENENSWN...

output:

78807461945

result:

ok single line: '78807461945'

Test #77:

score: 62
Accepted
time: 3ms
memory: 13868kb

input:

8008 35666788
SWENSSEESEWNENNENNWWWSEWSNEESEEEWNNNENSEENEWENNNSSNEWWSEWSNEWNWSENEWWEWSESNWWWWESNSEEWNWSNNNEWNNEENESESSNNNESNEWNWNEWWNSWNNSWSSSSSENSWSNSSSENESWSSEWNWSENNEWNEWNESWSSSNSSWESWNESENSWNESNEWSESWWSSEEEWWWWWWEWNNENNESNEWWNSWNNNNWSESNENSSEWWNNWEWSSWNNSNSNEWNWSSWSESESEENESWSNNWENNEEESWEEWESENN...

output:

1496

result:

ok single line: '1496'

Test #78:

score: 62
Accepted
time: 10ms
memory: 16044kb

input:

20000 800000000
NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN...

output:

7998375014998

result:

ok single line: '7998375014998'

Test #79:

score: 62
Accepted
time: 35ms
memory: 24408kb

input:

55555 999991929
NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN...

output:

1988983946932

result:

ok single line: '1988983946932'

Test #80:

score: 62
Accepted
time: 17ms
memory: 16292kb

input:

77777 1000000000
SWEWEWNWSSNWNWWEESNNSSWWNNNEEENSSNWSSWNENSWEWEWNESEESWWESSSWSWSNNSWSNSNNSWWNEEWWENNSWNWESSEWWEESNSWWNNNWSNEWNESWENNSNENNESWWEWESSSESNESNWWWWEEEWESEENSEESSENWSSWENEEWSEESEEWWNWNWWEEWESWSNWNESEWNWEEEENEWESNEWWSSSWWNSSNENESENWESWNEWWNSEESWSSSNWSWWEWNWNWESWSWSNSNSSSEEESWNSNWWSSESWNNNSNS...

output:

9759000005045

result:

ok single line: '9759000005045'

Test #81:

score: 62
Accepted
time: 8ms
memory: 16384kb

input:

100000 1112
WENSNWNESESNESESSNENNWWSESESSWSWESWSWNWWWENENEWNSWSNSNSSENEEEEWEEWNNSSSNSWSWNNEWSSENNNSNNSESSSWWSNNEWSESSEEENWWWEWEWNESWWSWNEESSESSNNSNNNNESEENEEENWSNENNWWENENESNWWEEEWSSWNWSWNENESEESEWESWSSSEEESSESWESEWWEEEWEESEEWWWWWNSEEENSNENNWNWESSEEWNESSWWWWNNSNESESSSNWSWSNENWSWENEWSSNEEWENSWNNWESWN...

output:

17164

result:

ok single line: '17164'

Test #82:

score: 62
Accepted
time: 27ms
memory: 18252kb

input:

100000 777777777
WNWNEWSSSNSSEESNEENENEWNSWWSEESWWNEWWWEWSSNNSESSWEEWNSSSNSEWEEESNSNEESWSWWEEWEWNSSSEEEESWNWWNSNSEWNEWSENNEESNWWNSNEEESSWSENEESWNNSWSWWNSSNEEWWEWNEWWWWSNWESNWNSNWNWNWNWWWENNNWNSSWEEWSEENEWNWNWWWSSWENSSWWEWSSENWWEESNSSNESNWWSSESWSWSWWNSSNEWNNSNNEESESWENWNNNENSEWWWNWSNENEENWEESESWNESEN...

output:

12022111099456

result:

ok single line: '12022111099456'

Test #83:

score: 62
Accepted
time: 20ms
memory: 15668kb

input:

99999 562000001
SNSNSSSSSESNEWSSENNENWNNNSENNESNSSSNSNSWNSNENSENSWNSESNNESSSENSSENSNWSSNESWSNNNNSNESNSESSSNSNSWSSNNSSNSNSNNNNSNNSSNESNNSSNNSSEEWNNNNESNSNWESSNSWSNSSSNENNSNNSESNNSNNSNNSNWWSEWSSSSSNEWSSSSENSSSNWNNSESSSSSNSSSNNESSNSWWSWNSSNSESSWNNNNENSSSSSNNNNSESWNNWNSSSNNNNSSSNENSSSSNESSNNNSWENESSNSSS...

output:

3067396014003

result:

ok single line: '3067396014003'

Test #84:

score: 62
Accepted
time: 31ms
memory: 18808kb

input:

100000 100010001
WNSWNSNNNENEWENEWNWWSWESENWWSESWWWEENSWEWEWEENWNESWNWWNWESNENNWWESNWESESSESWESSWWEWWSNSNNESEWESWEESEWNWNWWENENNWNWNWSNWEWWSEWSWNEEEENWSWSSWWNNWNNNESWWWEEESNWEEEWWESWNENNEWEESWWWWWNSWWSENSWSESSWWEWSNSSENSWNNENSNNWESNNNWSWSNNNSSWEEWWWSNSSNESWNWWSNNEWWEEWSNSWNENNESEWSNNNNWNSWSWWNSSNSSN...

output:

1624962496850

result:

ok single line: '1624962496850'

Test #85:

score: 62
Accepted
time: 31ms
memory: 18588kb

input:

100000 1000000000
WENWSSWNWWEWNESWWSSEWNWSSEEENENNNSWNESWSWNNWESNESEWWSWWSESNENEWENSWNWWSSNENSEWSEENWSEESESSWESWSENWSSWNNSNSSSSNENSNEWNENNENEENNEEWNEWNENEENNNSWEESWNSSSWENENSSENWSWNNEWESWNENESSWEENSNWSSSSNESENNESSEWWSEWSWSSWSWSESWWSEEWWSSWEWWNNWWEENNNESNSNESWEENSSESNWSNNSEENSWWESNEEENEENEWESEENEESEN...

output:

16310000000217

result:

ok single line: '16310000000217'

Test #86:

score: 62
Accepted
time: 56ms
memory: 22100kb

input:

99997 1000000000
NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN...

output:

24999624925002

result:

ok single line: '24999624925002'

Test #87:

score: 62
Accepted
time: 31ms
memory: 19564kb

input:

100000 998288773
NNWSWNWEENSEWWWWSWWESNWWNENWENWNEESEEWENSEEWEWSNEWWESESNNWWWNWENWSSWENSWWWEEENSNWESSNWWNSNNNSWWNNENENSWNSNSSSENWEWSEWNNESNNNSEWWSESSNEWWWESSWSNWSWNNEWWEESSENWSNSNNNWSWEWNENESNNSWWNSWWWEEWWSENESEWESWNENWWSNSNNSESEWNNNENNSEWESEWSEWNNNWENWEENWSSWENSWNEWEWSSNWEWNSESWWSNSWNENESENESEENWNN...

output:

18222763262379

result:

ok single line: '18222763262379'

Test #88:

score: 62
Accepted
time: 29ms
memory: 18168kb

input:

100000 1311007
WNWWSWNSSEEWWWSNWWSNEWNSWNSNSNEWWESSSESNEESNSNWNENESSNSWNSSEWEWSNWNWWWWNSWNESEEESWNWNWSNWWSNNNSNESNWSWEEWWENWEEEWWNENNSSWNSSENWSSSSNWENEWWWNNWSWENNSESWWWESWNSNNSNSWWNNWNESNNWEWEWWNWWWSENWSSWEEWWENEWENWESNWWSNESSSNWSWWNNWNENSSNSWNEWWSWENWSNNNNWWEWNSNSWSNNNEENESSEWNWWWNNEEENENWNWEESNWWN...

output:

19059420971

result:

ok single line: '19059420971'

Test #89:

score: 62
Accepted
time: 27ms
memory: 18404kb

input:

100000 1000000000
NEWSWSSWWENNENNEWSWSENNSESWSSENNWNWNNENWENSSNSESWSENENWEWSWNENNWESNNSSWNSWNSWNSSNNWWNSEWWESSNNENWEENSWSSSWESNWWWNNSWNWENNNEWNNSSSSWWWSWNEEEWEWENNNWSNEWEEEWWWNSSSSSEWNSWSNWEWWSWWSSWESEEWSWNSNNENEESNSNNSWWSNNNEENSENNNWEESSWWNWEESSSWEWNESSNWSWSWNENNNWWSENWWSNWEENNSWWWSNNESWWSNWWEWEEWW...

output:

15335000001305

result:

ok single line: '15335000001305'

Test #90:

score: 62
Accepted
time: 8ms
memory: 16260kb

input:

100000 811727364
NNESENWNWSENSNWNENNESSEEENEEENESNSWNSWSWNSNNSNNWWNSESWESWSENWSEESSSWESNWWWWNEWENNEWWNWESENENWEEWWNWNNSWWSSSEWENSWWSWSWSNEWSSWWESNWWWSNEWWSNWEWWESWWNEWSWWSWNSNEEWNESESWESWEENNENNSEWWSENNSNWESESSNWWWWEWSNESNEWEEWSSEWSWSNNEENNSNESNSNNESSNEENNNSESWEWNSESWWSENENESEWNNNSWSNNSWSWESWSWWEWWE...

output:

16990

result:

ok single line: '16990'

Test #91:

score: 62
Accepted
time: 29ms
memory: 18912kb

input:

100000 711111111
SWSNWNNWENEENNWWENESENNWEEENNSSSWSSEWSENEWEESWNSNSSNNSSWESEEESWSWWSSNWSESWEWWNNSESNWNESSNSWNNWNWWSESWSWENSESEENNWNWNEESENWEEWNEESWSNSSWESSSWNNNEWWWEWSEWWNWSWENEEESSWSWSSSEWSWNSWNSEWNSSWSWESEEWSENWNWSSEEENNEEWEWNNNNSWWWNEESSSSNWEEEWWWEWSWESWSSENNSSNESSWNWEENSSSNNWNESWWNEEWEESEEWSWNSW...

output:

12040533331529

result:

ok single line: '12040533331529'

Test #92:

score: 62
Accepted
time: 33ms
memory: 18980kb

input:

100000 314159265
WWEEWWENENWEWEEEENSESWWNNNEWSSNWENESWWWENEENSNESNNEWNWSWEEWEEWWNSWEESEENWWNWEEEEWWSEWWWWSEWESWSWSWEEEWWNSWNWNWSNSNNWWSSEEWNWWNWEWEWWEWSWSSSENWWEWEEWNNNNSENWNEWWSEEWEEESWNWSENSWEWNNNSEEWWWWEWSNSSESWWWSSNWWWNWNENEWEESWWENSSSWNSEWNSNSWNSEWWSNWENWENSENWNEEWESENWNSSWNNESENEESSNWWSESWSSWW...

output:

5398198650507

result:

ok single line: '5398198650507'

Test #93:

score: 62
Accepted
time: 28ms
memory: 18820kb

input:

100000 345354665
NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN...

output:

5139913479928

result:

ok single line: '5139913479928'

Test #94:

score: 62
Accepted
time: 23ms
memory: 17280kb

input:

100000 900000000
EWEWNWEEWWEENWWENWEENSSEWESENWWESSEWWNWWSENNEESSNENNWWNESEWSSWEWEEWSWSWNWNWNWWWWEWSSWEEEWEWWSWWWWSEWWEEWESEWWSWWWWEEWWSNWSENSEWNESWWEENWNNEENWSWWEWEWNNENWNESNEWWEWEWNEEEWEEEESESWNESWSEEEEWESEWEWWNEWEEWWSWNEENWSNENWWWSEEWSEEEWSNEWEWWESEENSWNEWSNNEWNWWSWWENNSWSWWEEENENWWESSESNWEWNNNNN...

output:

11561400001193

result:

ok single line: '11561400001193'

Test #95:

score: 62
Accepted
time: 26ms
memory: 17308kb

input:

100000 1000000000
ESSNNSNEESSWSNESWNWNSSSSNNSNNSNSEESNNNNSSSSWNNSSESNNNNSNSSSWSSSSWSSSSNNSNNSNNNSNSSESNSSNSWNSSSSNNNWNWSSNNSNSNNNWSWENNNNNNNSENSENWNNNWSNNSENNNNSNNNSNENSWSSESNNWNSWNSNSSENESESSSSSNNWSSNENSSSWNWSNNSSSNSSNNNSENSESSSSSSNSSSNNNNNNSSSSEWSESNSSWSNWNSNNENNWNNNSSSNSSSNEWSESNNSEENNNNNWSWNESSN...

output:

12034000002430

result:

ok single line: '12034000002430'

Test #96:

score: 62
Accepted
time: 58ms
memory: 22056kb

input:

100000 942967399
EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE...

output:

23573554445104

result:

ok single line: '23573554445104'

Test #97:

score: 62
Accepted
time: 81ms
memory: 30364kb

input:

100000 777039681
EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE...

output:

38850429920641

result:

ok single line: '38850429920641'

Test #98:

score: 62
Accepted
time: 3ms
memory: 14464kb

input:

99999 400761693
NNEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE...

output:

801623380

result:

ok single line: '801623380'

Test #99:

score: 62
Accepted
time: 63ms
memory: 33236kb

input:

100000 954516037
ESWSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS...

output:

954516037

result:

ok single line: '954516037'

Test #100:

score: 62
Accepted
time: 111ms
memory: 39728kb

input:

100000 1000000000
SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS...

output:

99997999950001

result:

ok single line: '99997999950001'

Extra Test:

score: 0
Extra Test Passed