#include <fstream>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <string.h>
#include <queue>
#include <math.h>
#include <set>
 
#define min(a,b) ((a<b)?a:b)
#define max(a,b) ((a<b)?b:a)
#define abs(a) ((a<0)?-a:a)
#define REP(i,a,b) \
	for (int i=a; i<=b; i++)
 
#define INF 10000000000001
 
using namespace std;
 
#define TEST
#ifndef TEST
ifstream fin ("vacation.in");
ofstream fout ("vacation.out");
#else
#define fin cin
#define fout cout
#endif
 
#define MAXN 200
 
typedef long long ll;
 
int n,k,m,q;
 
ll a[MAXN][MAXN];
 
int rez=0;
ll sum = 0;
 
void Floyd()
{
    REP(ic,0,n-1)
	{
        REP(jc,0,n-1)
		{
            REP(kc,0,n-1)
			{
                if ((kc==jc) || (kc==ic) || (ic==jc)) continue;
                else  a[jc][kc]=min(a[jc][kc],a[jc][ic]+a[ic][kc]);
			}
		}
	}
}
 
int main()
{
	fin>>n>>m>>k>>q;
 
	REP(i,0,n-1)
		REP(j,0,n-1)
			a[i][j]=INF;
 
	for (int i=0; i<n; i++)
		a[i][i]=0;
 
	for (int i=0; i<m; i++)
	{
		int x,y,c;
		fin>>x>>y>>c;
		a[x-1][y-1]=c;
	}
 
	Floyd();
 
	for (int i=0; i<q; i++)
	{
		int x,y;
		fin>>x>>y;
		ll r = INF;
		for (int j=0; j<k; j++)
			r = min(r, a[x-1][j]+a[j][y-1]);
		if (r==INF) continue;
		rez++;
		sum+=r;
	}
 
	fout<<rez;
	fout<<'\n';
	fout<<sum;
	fout<<'\n';
 
    return 0;
}

I2luY2x1ZGUgPGZzdHJlYW0+CiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPHN0cmluZz4KI2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPHN0cmluZy5oPgojaW5jbHVkZSA8cXVldWU+CiNpbmNsdWRlIDxtYXRoLmg+CiNpbmNsdWRlIDxzZXQ+CiAKI2RlZmluZSBtaW4oYSxiKSAoKGE8Yik/YTpiKQojZGVmaW5lIG1heChhLGIpICgoYTxiKT9iOmEpCiNkZWZpbmUgYWJzKGEpICgoYTwwKT8tYTphKQojZGVmaW5lIFJFUChpLGEsYikgXAoJZm9yIChpbnQgaT1hOyBpPD1iOyBpKyspCiAKI2RlZmluZSBJTkYgMTAwMDAwMDAwMDAwMDEKIAp1c2luZyBuYW1lc3BhY2Ugc3RkOwogCiNkZWZpbmUgVEVTVAojaWZuZGVmIFRFU1QKaWZzdHJlYW0gZmluICgidmFjYXRpb24uaW4iKTsKb2ZzdHJlYW0gZm91dCAoInZhY2F0aW9uLm91dCIpOwojZWxzZQojZGVmaW5lIGZpbiBjaW4KI2RlZmluZSBmb3V0IGNvdXQKI2VuZGlmCiAKI2RlZmluZSBNQVhOIDIwMAoKdHlwZWRlZiBsb25nIGxvbmcgbGw7CgppbnQgbixrLG0scTsKCmxsIGFbTUFYTl1bTUFYTl07CgppbnQgcmV6PTA7CmxsIHN1bSA9IDA7Cgp2b2lkIEZsb3lkKCkKewogICAgUkVQKGljLDAsbi0xKQoJewogICAgICAgIFJFUChqYywwLG4tMSkKCQl7CiAgICAgICAgICAgIFJFUChrYywwLG4tMSkKCQkJewogICAgICAgICAgICAgICAgaWYgKChrYz09amMpIHx8IChrYz09aWMpIHx8IChpYz09amMpKSBjb250aW51ZTsKICAgICAgICAgICAgICAgIGVsc2UgIGFbamNdW2tjXT1taW4oYVtqY11ba2NdLGFbamNdW2ljXSthW2ljXVtrY10pOwoJCQl9CgkJfQoJfQp9CgppbnQgbWFpbigpCnsKCWZpbj4+bj4+bT4+az4+cTsKCglSRVAoaSwwLG4tMSkKCQlSRVAoaiwwLG4tMSkKCQkJYVtpXVtqXT1JTkY7CgoJZm9yIChpbnQgaT0wOyBpPG47IGkrKykKCQlhW2ldW2ldPTA7CgoJZm9yIChpbnQgaT0wOyBpPG07IGkrKykKCXsKCQlpbnQgeCx5LGM7CgkJZmluPj54Pj55Pj5jOwoJCWFbeC0xXVt5LTFdPWM7Cgl9CgoJRmxveWQoKTsKCglmb3IgKGludCBpPTA7IGk8cTsgaSsrKQoJewoJCWludCB4LHk7CgkJZmluPj54Pj55OwoJCWxsIHIgPSBJTkY7CgkJZm9yIChpbnQgaj0wOyBqPGs7IGorKykKCQkJciA9IG1pbihyLCBhW3gtMV1bal0rYVtqXVt5LTFdKTsKCQlpZiAocj09SU5GKSBjb250aW51ZTsKCQlyZXorKzsKCQlzdW0rPXI7Cgl9CgoJZm91dDw8cmV6OwoJZm91dDw8J1xuJzsKCWZvdXQ8PHN1bTsKCWZvdXQ8PCdcbic7CgogICAgcmV0dXJuIDA7Cn0=

NTAgNzAgMiAxMDAwCjM4IDQgMjQ4MzM1CjQ0IDM5IDE5MjEzCjIwIDkgODE4MDgKNDAgNDUgNDcwNzg3CjEgMzcgNDk4NjQ0CjQ5IDMyIDQxNjMwNAoyMyAzMyA0NDc4OTMKNDAgMzcgMzM2MzQzCjQ2IDI2IDY2NTg1MQo0OSAzMCA2OTM3MTAKOCA2IDQ1Mjk0NQo1IDQxIDExNTc5MwoyIDE1IDQ5MDgzNQoxMyAzNSAxMjUxNTIKNDIgNDQgMTk5ODMxCjQ0IDI4IDU5MTM5NAoyIDM3IDgzOTU4NwozNiAxOSAyNzU5OTUKMzEgMjYgOTUzMTQKNDYgMjAgNzg4NzI4CjMyIDQ3IDkxMjg1CjEgNDYgOTA5MTAzCjM5IDIyIDI2MDk5MgoxIDMgNzU5MDI1CjQyIDIgNzAwNjMwCjUgMzAgMjcxODUyCjE5IDQ3IDkzNTYwMgoxIDI3IDU4NDU1OQo0NSAxMyA5OTgxODUKMiAyMCA0ODcwNTQKMTYgMjIgODA2MjUyCjEgMTUgMzQ2NjMwCjEgNDAgNTQzMzY4CjQ2IDI1IDQ4MjgwNwoxNCA2IDc2MjM0MQoyMCAxNCA0Njc2MjQKNDkgMzggOTA4OTMyCjIgNDkgNTU5ODEyCjIgMzEgODE2ODAwCjI1IDcgNTIyMDU4CjIgNDMgODMxMTYzCjIxIDM4IDY4Mzg1MgoyIDcgNjI4NTU2CjIgMjMgOTUyNTAzCjQzIDMgNjE5MTQ3CjYgNDAgNDczODY0CjMwIDcgMzE5MjcxCjE4IDMwIDc4NTQyNgoyMSAxIDcxOTAzOQo0NyAxOSA2OTMzOTAKMTYgMjkgNjIzNDQ1CjI3IDQ2IDg3MzM1Mgo0NCA0OCA1MjA5NTIKMjYgMzggMzE0NjEKMiAxNCA2MDI2NDcKMjMgMTMgNDQzOTUwCjIyIDE5IDQzMDE1OAozMSA0NyAyMjYyMDUKMTQgMjMgNzk2MzI1CjEgMjIgNDM2ODQyCjQ3IDYgNTUwNzk5CjIgNDggODIwMjQ2CjM5IDQ5IDE4NjM2NgoyIDE3IDYwNzEwCjQgMjkgMjU3NTc5CjIgMzkgNjUyNzY1CjMzIDI1IDM5NzI3NQoyIDEyIDg0MTk0NgoyOSAzNyA4NzkyODYKMjggMzEgNTg2ODMyCjEgNDgKMSAyNAoxMSAyCjI5IDMyCjI0IDIKMTIgMgoyIDEKMTUgMjcKMzcgMTcKMiAyMwoyMyAyCjEgMjUKNSAxNgoxIDIKMSAyMAoyMSAxCjggMwoxIDQ3CjIgMzIKNiAyNQozOSA0CjExIDIKMSA0MAoyIDI4CjMgMzgKNCA4CjIgMQo0MCA1CjIgMQozMiA4CjEgMTQKMjIgMTQKMiAxCjkgMQozOCAyNAoyIDEwCjE1IDQ2CjEgMgozNiA5CjQ2IDIKMzUgMQoxNyAxOQo0NiA1MAoyIDM0CjIzIDEKMiAxCjM1IDIKMiA0OQoyIDEKMSAyCjIgMjEKMSAxNgo3IDEKNDQgMjkKMSAzOAoyNyA0NgozMyAxCjEgMgo4IDIKNDQgNDEKMSA0NQoxOCAyCjIxIDM5CjQzIDEKNDkgNQoyIDI2CjEgMgoxIDI0CjMzIDEKNCA0MAoxNiAzCjE5IDIyCjIgNwoxMCAxCjE4IDQ4CjIgMjgKMiAxCjIgMQo3IDIKMjggMQozNCAyCjEgMgo0NyA0OQo0MyAxMAoxOSAyCjIgOAo0MiAyCjE1IDM2CjEgMTkKMiAyMAoyIDM0CjI4IDEKNDkgMzUKNDcgMgoxMSAzMQoyIDkKMiAxCjIgNDIKNDcgMQoyIDI4CjEgOQoxIDExCjIgMjEKMiA1CjIgMwoyIDI3CjEgNDEKMiAyMQo0MyAxMgo0NSA0NAoyIDQzCjEgMgozIDEKMSAyCjE3IDEKMSAyOAozOCA0NQoxIDI0CjQ4IDIKMiAxCjIgMzMKOSAxMQozNiAyOQoxIDE5CjEgMzAKMiAzCjE3IDgKMjMgNDQKMTUgMzkKOSAxNAoxIDIKMSAxOAoxMSAxCjI5IDQ2CjEgMTYKMiAxNQoyIDM2CjIzIDMzCjEgMzQKMTEgMgoyIDI5CjEyIDE5CjMyIDEKNDIgMQoyIDEKNDIgMjMKMyA1CjM2IDEKMTUgMgo0OCA0OQo0MiAxCjQgMgoxNiAyMQoyIDEKNDMgMjQKMjcgMQoyOCAxCjIgMQozNCAyCjEgMgoxNCAyCjIzIDIKMiAyOQoxMSAyCjIgNDQKMTAgMQoyIDEKMiAxCjM0IDEKMjAgMTgKMzYgMQoyIDI2CjQwIDEKNTAgMQoyIDI4CjMxIDIyCjIgMQo0OCAxCjQ3IDEKMTEgMgoyIDMzCjIyIDEKMSAxNwoyIDExCjIgMQoxNSAyNQoxIDE5CjEgMgoyMyAzCjExIDIKNDcgMjkKNiAxCjExIDIKMSAyCjEgMzUKMjkgMgozNCAyCjIyIDE4CjUgMjEKNDggMQozOSAzMwoyNSAxCjIgMQoyIDQ0CjIgMTcKMiAyOQoyIDQ0CjQ3IDIKMiAyNQo0NyAyNgoxIDIKMjAgMjQKMiA1MAozNCA0MQozNiAxCjEgMjAKMzQgMQoyMiAxOQo0NCAyCjQ4IDEKMiA0OAoyIDEKNDMgMTkKMiAxCjQxIDIKMSAzMQoxOSAyCjMyIDcKMiAxCjM2IDE5CjM2IDIKMzQgMgoxMiAyCjEgMjcKMzQgNDgKMSA3CjQzIDEKMSAyCjMyIDIKMSA0MQoyIDQzCjEgMzMKMiAxCjEgNAoyNiAxMwoxMCAxCjE2IDIKNDIgMgoxIDMxCjEgMgoxIDIKMiAxCjM4IDEKNDYgMQoyIDM4CjEyIDkKMzYgMgoyIDEKMiAyNQo0OCAyCjIgMTAKMiAxMgoyOCAyCjIgMzcKMSAyCjMxIDIKMTEgMjcKMzQgMTIKNDQgMQoxMSAxOQo4IDQwCjE0IDgKNDYgMzUKMTAgMzkKMTggMTIKMiAxCjIgNwoyIDEKMTEgMzQKNDEgMTYKMiAxMQoxIDIKMzIgMQoxNSA2CjI3IDEKMTggMzcKNSA4CjIgMQoxIDIKMzcgNTAKMzAgMjYKNiAzOAoyMSAzMgoxIDUwCjE2IDEKMSAzMwoyMCAxOQozMiAxCjQxIDIKMiAxCjIgNDIKMTMgMzUKOSAzOAoyIDE0CjEgMzMKMiAxMwoxIDM1CjQ0IDExCjYgMjcKMTEgNTAKMzIgMQoyIDMwCjQ3IDM2CjE0IDcKMSA5CjIgMjgKMTAgMTMKMTUgMQoyMyAxCjQzIDQyCjI0IDEKMzAgMzcKMSAxNAoyMiAyCjEgMzEKMTMgMQoxMyA0OAoxMSAxCjkgMTgKMjUgMQoyIDYKMSAyCjMxIDEzCjggMQo3IDIKMSAxNQoxIDQ0CjMgMjcKMiA1MAoxIDQxCjEgMzEKMSAyNAoyIDQxCjQ5IDEKMzEgMQozMSAyMwoyIDM5CjI1IDE4CjI0IDIKMTMgMzAKMTYgMzEKMTMgMQo0NyAxCjQ3IDIyCjEwIDEKMSA0MQoxOSAyCjI5IDIKNDQgMjQKMiA0MAo0MSAzMQo0MCAyCjEgMgoyIDEKMjQgMTAKMjggMQoyOCAyCjIyIDQwCjEgMzYKMSA0NwoxIDE2CjI4IDIKMiAxCjQ1IDUKMjYgMgo0NiAzMwo0MSAyCjExIDM0CjIgMjMKMSAxMgoxOSAxMgoyMiAyCjMxIDM1CjI3IDEKMzEgMjMKMiAxOAo1MCAxCjEgMTcKMzIgNTAKMiAxCjEgMgoyOCAxCjEgMjUKMjggMgoxIDIKMSAxNAoyIDMwCjI5IDE1CjggMQoyIDM5CjQgMQoyIDUKNSAxCjIwIDI4CjQgOAoyIDEKMzkgMQoyIDIzCjEgOAo0MSAyCjEgMgo1IDEKMTMgMzQKMSAyCjMzIDE3CjM0IDIKMzAgMgoyIDIyCjI3IDEKMjEgMgoxIDIKMTggMgoyIDMzCjQ0IDQ4CjMyIDExCjI3IDIKNDUgMQoyIDYKMTcgMTEKMSAyCjEgNDcKMSA5CjEgNDkKMzYgMQozIDI2CjE4IDEKNDEgNgoxMyAzMQo1IDEKMjAgMzEKMTkgMgoxNiAyCjEzIDM1CjIwIDIKNDggMQozNyAxCjE0IDMKMzUgMgo0MSAzOQo0NCAyCjM4IDQzCjQ0IDE4CjEgMjAKNDkgNDUKMiAyMAo0OSAyCjI5IDQzCjE1IDIKMSA1MAoyIDEKMSAyCjMxIDI1CjEgMTEKMiA0NgoyNyAxCjI1IDgKNTAgMQozOSAxCjI0IDUwCjM5IDMxCjEgMjMKMzEgMgoxNCAyMQoxIDE3CjE2IDIKMSAxMQoyIDIxCjEgMgoyNyAyNAoyIDEKMSAzNQozMiAyCjIgMwoyIDEzCjIgMQoxIDM4CjM2IDEKMSAyCjI2IDEKMiAyNQo5IDQ4CjIgNQozMyAyOAoyOSAzNgo0MiAxMwoxIDIKOSAyCjEgMzIKMjAgMgoyIDEKMTkgMQoxIDI1CjEgMzEKMSAxNAoyMiAxCjI4IDM2CjExIDQKMSAzNAoxMiAxCjEgMgoyNiAyCjIgMTkKNDUgMTQKNDQgMQo1IDQ0CjMwIDIKMTEgMQozOSAyCjEgMgoxIDQKMiA0NQoyMCAzCjEgMzEKMjYgMgoyIDMxCjIgOAozIDIKMSAyCjEgMjgKMSA3CjM4IDIyCjI2IDI0CjIgMQoyIDM4CjE2IDIKMiA1CjIwIDM2CjMwIDEKMSAyMwoyIDUwCjIgMTkKNyAxCjM1IDIKMSAyMgo0MiAxNQo0NSAxCjMxIDMwCjQ2IDI4CjExIDI3CjEgMTIKNSAyCjIgMzYKNCA0MgoxIDIxCjUgMzMKMzQgMTcKMSAyNQoxOCAxNAozNSA2CjEgMgoxIDIKMTUgMQoyIDEyCjIgMQoyIDQzCjEgNDMKMSA1CjQ5IDIKMTUgMQoyMSA4CjIgMzYKMTkgMjAKMzMgMTAKMSA0NAoxIDIKNDIgMTcKMSAyCjIgMzUKMiA0NgoxIDMwCjIgMQoxNiAyCjEgMzAKMSAyNgoyIDQxCjM4IDEKMSA0Ngo0MSA0NAozNCA1MAo4IDE1CjIgMQoxIDIKMTcgMgoxMCAxCjI2IDEKNDcgMTQKMiAxCjIyIDEKMjIgMzcKNDkgMzQKNDAgMQoyIDM4CjcgOQozMCA0OQoxMyAyCjEgMzYKMzQgMTkKMiAzMQoyIDEKMiAxCjMzIDEKMTEgMzIKMiAzMQoxIDI3CjM4IDgKMTMgMTYKMTUgMQoyNSAxCjE5IDEKMSA0CjIgMTMKMiAxCjI3IDIxCjM5IDMyCjQ5IDEKMzAgMQo1MCAxCjcgMQoxOSAxCjIgMTUKNDUgMzAKMiA2CjIzIDIKNDMgMzMKMSAyCjIgNDUKMSAyMQozMiAyMQoyIDM4CjIgMQozMiA0MwozMSAyMAoyIDQwCjEgNDYKOSAxCjE2IDEKMyAyCjIgMjgKMyAyNgoyIDEKNDAgNAoyIDEKMzUgMQoyIDEKMjggMgoxNyA0CjIgMjYKMzAgMTkKMSAyCjEgNQo2IDIyCjEgNDkKMSA1CjE1IDEKMTkgMgo0NiAyCjM5IDEKNyAyOQoxIDYKMiAxCjMgMjUKMzEgNDEKMiAxCjIgNDgKMjAgMwoyIDQ4CjI1IDIKMiAyNAoyIDEKNSA0OAoyIDQ4CjI1IDIKNDggMjEKMSAyCjE2IDIKNiAzNwoyMyA0MgozNyA3CjIgNDAKMjMgMTMKNiA5CjEgMjQKMiAxCjMyIDIKMSAyCjEgMzEKMSAyMgoyNyAzMQoyIDEKMTkgMTQKNDIgMTEKMzAgOQoyOSAxOQoxIDIKMSA0MgoyMSAxCjIgMQo0OCA4CjQyIDIKNDIgMgo0OSAxCjQgMQoyNiAyCjIgMjYKNDAgMgoyMSAyCjEzIDE4CjM2IDEKMiAxCjMwIDIKMTEgMgoyNCAzMgoxNyAyCjMyIDEKMzggMjEKNDggMTgKMSAxNgoyNCAzNgozMyA1MAoyNCAxCjIgNDkKMiAxCjEgMjAKNTAgMjAKNDAgMQo0OSAyCjEgMgoxOCAxNgoyIDM5CjEgMgoxMSAyCjEgNDIKMiA0NQoyOSAxCjI2IDEKMSAyCjMwIDMKMTEgMQoxIDQ4CjEgMgoyIDEKMTEgMQoxIDIKMiAxMQoyIDM0CjcgMTYKMSAyCjI4IDM1CjIgMTMKMTAgMTUKMiA0OAoyIDQ3CjIwIDkKMSAzNgoyIDQxCjEgMzEKMzIgMjgKMSAyNAoxIDE2CjE3IDI1CjE1IDIKMSA0OQo1MCAxCjEgNDAKMiAxOAoyIDEyCjEgMTgKNDUgMQoxIDI0CjIgMTMKMTkgNDgKMTIgMjUKMTQgMgozNiAxCjMyIDIKMTkgMTQKNyAxCjI1IDIKMiA2CjE3IDgKMjggMTUKMSAyCjEyIDIKMyAzMQozMSAyCjIgNAozNyA0NQo5IDE4CjIgMTkKMjIgNDAKMSAzNAo1MCAxMwoxIDI0CjIgMQoyIDMxCjEyIDgKMjggMQoyMiA0CjIgNDMKMSAxOAo1MCA1CjIgMjQKNDMgNDEKNCAyCjEgMjIKMiAzNAoxIDIKNDcgMjcKNDIgOQoxIDM1CjMgMTUKMiA1CjIwIDIKMiA3CjE2IDIKMSA0NAozMSAyMQoyIDEKMSAyCjI2IDEKMiA0NgoyIDI2CjI3IDEKMSAyCjIgMQoyIDEKMSA0OQoyIDEKMSA2CjIgMTkKMSAyNQoyOCAzNQoyNSAyNwoxMiAxOQo0MSAxCjMgMQo5IDEKMjkgMzkKMSAyCjIzIDQxCjIgMTAKMiAyNwoyIDEKMSA0MgoyIDE5CjM4IDExCjQ5IDEKNDIgMQozNCAxCjM1IDI1CjIzIDM4CjI1IDQ1CjIgMQozMiAyCjIgNgoxIDUKMjcgMQoxIDIzCjQgMTcKNDQgMTcKNDggMQoyIDM5CjEgNDkKMSAzOQoxIDUwCjIgNwoxIDI5CjMwIDEKMiA0Nwo0NCAxCjEgMjUKMSAxOQo0MiA0NAo0MSAxMgoxIDM2CjQ1IDIKMzkgMQo3IDE5CjEgMzIKMiAzNwo0NSAxMwoxMCAxCjIgMQoyIDIwCjIyIDEKMSAyCjggMQoyIDYKMzYgMQozOSA0CjIgMjMKMiAxMwo0MCAzMwoxIDIKMjggMTAKMzggMQozOCAyCjEgMgo0NSAyCjEgMgozMCAzOQoyIDEKMTUgMgo0IDEKMiAxCjMzIDE5CjEzIDIKMTUgNDYKMSAyCjEgMgoxMiA0MAo0OCAxCjEwIDIKNDkgMjYKNDEgMjEKMjIgNwoxIDI0CjEgMzMKMSAyCjIgMQoyIDEKMSAyCjIyIDQxCjIgMzIKMjIgMQoxIDM3CjE1IDEKMzggMQozMiA4CjE3IDEKMjMgMTYKNDUgMQoyIDEKNDIgMzQKMjggMzIKMjYgMTQKMzcgMQozNCAyCjMwIDIKMSAzNwoyIDEKMiA2CjE0IDEKMiAxCjM0IDIKNyAyCjEgMzcKMzEgMzAKNDQgNTAKNDcgNTAKNiAyCjIyIDE2CjE2IDIKMzUgMQozOCA0MwoxOCAzCjIgMQoyIDkKMyAxCjIgMQo0NSAyCjEgNDcKMiAxMwoxIDIKNCAzMwo0OSAyOQoxIDMxCjE1IDM5CjM3IDcKMSAxNQoyIDM4CjI3IDIKMzYgMgozMyAxCjEgNDgKMSAyCjEgNAoxIDkKMSAyCjMwIDIKNDMgMTUKMjcgMgoyIDM5CjM4IDgKNTAgMQoyNiAzNwozNyAyMgo4IDIKMzcgMgoyIDYK

50 70 2 1000
38 4 248335
44 39 19213
20 9 81808
40 45 470787
1 37 498644
49 32 416304
23 33 447893
40 37 336343
46 26 665851
49 30 693710
8 6 452945
5 41 115793
2 15 490835
13 35 125152
42 44 199831
44 28 591394
2 37 839587
36 19 275995
31 26 95314
46 20 788728
32 47 91285
1 46 909103
39 22 260992
1 3 759025
42 2 700630
5 30 271852
19 47 935602
1 27 584559
45 13 998185
2 20 487054
16 22 806252
1 15 346630
1 40 543368
46 25 482807
14 6 762341
20 14 467624
49 38 908932
2 49 559812
2 31 816800
25 7 522058
2 43 831163
21 38 683852
2 7 628556
2 23 952503
43 3 619147
6 40 473864
30 7 319271
18 30 785426
21 1 719039
47 19 693390
16 29 623445
27 46 873352
44 48 520952
26 38 31461
2 14 602647
23 13 443950
22 19 430158
31 47 226205
14 23 796325
1 22 436842
47 6 550799
2 48 820246
39 49 186366
2 17 60710
4 29 257579
2 39 652765
33 25 397275
2 12 841946
29 37 879286
28 31 586832
1 48
1 24
11 2
29 32
24 2
12 2
2 1
15 27
37 17
2 23
23 2
1 25
5 16
1 2
1 20
21 1
8 3
1 47
2 32
6 25
39 4
11 2
1 40
2 28
3 38
4 8
2 1
40 5
2 1
32 8
1 14
22 14
2 1
9 1
38 24
2 10
15 46
1 2
36 9
46 2
35 1
17 19
46 50
2 34
23 1
2 1
35 2
2 49
2 1
1 2
2 21
1 16
7 1
44 29
1 38
27 46
33 1
1 2
8 2
44 41
1 45
18 2
21 39
43 1
49 5
2 26
1 2
1 24
33 1
4 40
16 3
19 22
2 7
10 1
18 48
2 28
2 1
2 1
7 2
28 1
34 2
1 2
47 49
43 10
19 2
2 8
42 2
15 36
1 19
2 20
2 34
28 1
49 35
47 2
11 31
2 9
2 1
2 42
47 1
2 28
1 9
1 11
2 21
2 5
2 3
2 27
1 41
2 21
43 12
45 44
2 43
1 2
3 1
1 2
17 1
1 28
38 45
1 24
48 2
2 1
2 33
9 11
36 29
1 19
1 30
2 3
17 8
23 44
15 39
9 14
1 2
1 18
11 1
29 46
1 16
2 15
2 36
23 33
1 34
11 2
2 29
12 19
32 1
42 1
2 1
42 23
3 5
36 1
15 2
48 49
42 1
4 2
16 21
2 1
43 24
27 1
28 1
2 1
34 2
1 2
14 2
23 2
2 29
11 2
2 44
10 1
2 1
2 1
34 1
20 18
36 1
2 26
40 1
50 1
2 28
31 22
2 1
48 1
47 1
11 2
2 33
22 1
1 17
2 11
2 1
15 25
1 19
1 2
23 3
11 2
47 29
6 1
11 2
1 2
1 35
29 2
34 2
22 18
5 21
48 1
39 33
25 1
2 1
2 44
2 17
2 29
2 44
47 2
2 25
47 26
1 2
20 24
2 50
34 41
36 1
1 20
34 1
22 19
44 2
48 1
2 48
2 1
43 19
2 1
41 2
1 31
19 2
32 7
2 1
36 19
36 2
34 2
12 2
1 27
34 48
1 7
43 1
1 2
32 2
1 41
2 43
1 33
2 1
1 4
26 13
10 1
16 2
42 2
1 31
1 2
1 2
2 1
38 1
46 1
2 38
12 9
36 2
2 1
2 25
48 2
2 10
2 12
28 2
2 37
1 2
31 2
11 27
34 12
44 1
11 19
8 40
14 8
46 35
10 39
18 12
2 1
2 7
2 1
11 34
41 16
2 11
1 2
32 1
15 6
27 1
18 37
5 8
2 1
1 2
37 50
30 26
6 38
21 32
1 50
16 1
1 33
20 19
32 1
41 2
2 1
2 42
13 35
9 38
2 14
1 33
2 13
1 35
44 11
6 27
11 50
32 1
2 30
47 36
14 7
1 9
2 28
10 13
15 1
23 1
43 42
24 1
30 37
1 14
22 2
1 31
13 1
13 48
11 1
9 18
25 1
2 6
1 2
31 13
8 1
7 2
1 15
1 44
3 27
2 50
1 41
1 31
1 24
2 41
49 1
31 1
31 23
2 39
25 18
24 2
13 30
16 31
13 1
47 1
47 22
10 1
1 41
19 2
29 2
44 24
2 40
41 31
40 2
1 2
2 1
24 10
28 1
28 2
22 40
1 36
1 47
1 16
28 2
2 1
45 5
26 2
46 33
41 2
11 34
2 23
1 12
19 12
22 2
31 35
27 1
31 23
2 18
50 1
1 17
32 50
2 1
1 2
28 1
1 25
28 2
1 2
1 14
2 30
29 15
8 1
2 39
4 1
2 5
5 1
20 28
4 8
2 1
39 1
2 23
1 8
41 2
1 2
5 1
13 34
1 2
33 17
34 2
30 2
2 22
27 1
21 2
1 2
18 2
2 33
44 48
32 11
27 2
45 1
2 6
17 11
1 2
1 47
1 9
1 49
36 1
3 26
18 1
41 6
13 31
5 1
20 31
19 2
16 2
13 35
20 2
48 1
37 1
14 3
35 2
41 39
44 2
38 43
44 18
1 20
49 45
2 20
49 2
29 43
15 2
1 50
2 1
1 2
31 25
1 11
2 46
27 1
25 8
50 1
39 1
24 50
39 31
1 23
31 2
14 21
1 17
16 2
1 11
2 21
1 2
27 24
2 1
1 35
32 2
2 3
2 13
2 1
1 38
36 1
1 2
26 1
2 25
9 48
2 5
33 28
29 36
42 13
1 2
9 2
1 32
20 2
2 1
19 1
1 25
1 31
1 14
22 1
28 36
11 4
1 34
12 1
1 2
26 2
2 19
45 14
44 1
5 44
30 2
11 1
39 2
1 2
1 4
2 45
20 3
1 31
26 2
2 31
2 8
3 2
1 2
1 28
1 7
38 22
26 24
2 1
2 38
16 2
2 5
20 36
30 1
1 23
2 50
2 19
7 1
35 2
1 22
42 15
45 1
31 30
46 28
11 27
1 12
5 2
2 36
4 42
1 21
5 33
34 17
1 25
18 14
35 6
1 2
1 2
15 1
2 12
2 1
2 43
1 43
1 5
49 2
15 1
21 8
2 36
19 20
33 10
1 44
1 2
42 17
1 2
2 35
2 46
1 30
2 1
16 2
1 30
1 26
2 41
38 1
1 46
41 44
34 50
8 15
2 1
1 2
17 2
10 1
26 1
47 14
2 1
22 1
22 37
49 34
40 1
2 38
7 9
30 49
13 2
1 36
34 19
2 31
2 1
2 1
33 1
11 32
2 31
1 27
38 8
13 16
15 1
25 1
19 1
1 4
2 13
2 1
27 21
39 32
49 1
30 1
50 1
7 1
19 1
2 15
45 30
2 6
23 2
43 33
1 2
2 45
1 21
32 21
2 38
2 1
32 43
31 20
2 40
1 46
9 1
16 1
3 2
2 28
3 26
2 1
40 4
2 1
35 1
2 1
28 2
17 4
2 26
30 19
1 2
1 5
6 22
1 49
1 5
15 1
19 2
46 2
39 1
7 29
1 6
2 1
3 25
31 41
2 1
2 48
20 3
2 48
25 2
2 24
2 1
5 48
2 48
25 2
48 21
1 2
16 2
6 37
23 42
37 7
2 40
23 13
6 9
1 24
2 1
32 2
1 2
1 31
1 22
27 31
2 1
19 14
42 11
30 9
29 19
1 2
1 42
21 1
2 1
48 8
42 2
42 2
49 1
4 1
26 2
2 26
40 2
21 2
13 18
36 1
2 1
30 2
11 2
24 32
17 2
32 1
38 21
48 18
1 16
24 36
33 50
24 1
2 49
2 1
1 20
50 20
40 1
49 2
1 2
18 16
2 39
1 2
11 2
1 42
2 45
29 1
26 1
1 2
30 3
11 1
1 48
1 2
2 1
11 1
1 2
2 11
2 34
7 16
1 2
28 35
2 13
10 15
2 48
2 47
20 9
1 36
2 41
1 31
32 28
1 24
1 16
17 25
15 2
1 49
50 1
1 40
2 18
2 12
1 18
45 1
1 24
2 13
19 48
12 25
14 2
36 1
32 2
19 14
7 1
25 2
2 6
17 8
28 15
1 2
12 2
3 31
31 2
2 4
37 45
9 18
2 19
22 40
1 34
50 13
1 24
2 1
2 31
12 8
28 1
22 4
2 43
1 18
50 5
2 24
43 41
4 2
1 22
2 34
1 2
47 27
42 9
1 35
3 15
2 5
20 2
2 7
16 2
1 44
31 21
2 1
1 2
26 1
2 46
2 26
27 1
1 2
2 1
2 1
1 49
2 1
1 6
2 19
1 25
28 35
25 27
12 19
41 1
3 1
9 1
29 39
1 2
23 41
2 10
2 27
2 1
1 42
2 19
38 11
49 1
42 1
34 1
35 25
23 38
25 45
2 1
32 2
2 6
1 5
27 1
1 23
4 17
44 17
48 1
2 39
1 49
1 39
1 50
2 7
1 29
30 1
2 47
44 1
1 25
1 19
42 44
41 12
1 36
45 2
39 1
7 19
1 32
2 37
45 13
10 1
2 1
2 20
22 1
1 2
8 1
2 6
36 1
39 4
2 23
2 13
40 33
1 2
28 10
38 1
38 2
1 2
45 2
1 2
30 39
2 1
15 2
4 1
2 1
33 19
13 2
15 46
1 2
1 2
12 40
48 1
10 2
49 26
41 21
22 7
1 24
1 33
1 2
2 1
2 1
1 2
22 41
2 32
22 1
1 37
15 1
38 1
32 8
17 1
23 16
45 1
2 1
42 34
28 32
26 14
37 1
34 2
30 2
1 37
2 1
2 6
14 1
2 1
34 2
7 2
1 37
31 30
44 50
47 50
6 2
22 16
16 2
35 1
38 43
18 3
2 1
2 9
3 1
2 1
45 2
1 47
2 13
1 2
4 33
49 29
1 31
15 39
37 7
1 15
2 38
27 2
36 2
33 1
1 48
1 2
1 4
1 9
1 2
30 2
43 15
27 2
2 39
38 8
50 1
26 37
37 22
8 2
37 2
2 6