#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

struct zamestnanec {
	bool vedouci;		// Je vedoucí? Má své podřízené?
	unsigned char dalsi;	// Který podřízený dostane další úkol?
	size_t podrizeni[2];	// Indexy podřízených
	size_t nadrizenych;	// Počet nevyřešených nadřízených
	unsigned long long ukolu; // Počet úkolů, co má vykonat
};

int main(int argc, const char *argv[]) {
	size_t zamestnancu, vedoucich, reditel;
	unsigned long long ukolu;
	scanf("%zu%zu%zu%llu\n", &zamestnancu, &vedoucich, &reditel, &ukolu);
	struct zamestnanec *zamestnanci = calloc(zamestnancu, sizeof *zamestnanci);
	zamestnanci[reditel].ukolu = ukolu;
	for (size_t i = 0; i < vedoucich; i ++) {
		size_t vedouci, prvni, druhy, zacinajici;
		scanf("%zu%zu%zu%zu\n", &vedouci, &prvni, &druhy, &zacinajici);
		struct zamestnanec *v = &zamestnanci[vedouci];
		v->vedouci = true;
		v->dalsi = zacinajici;
		v->podrizeni[0] = prvni;
		v->podrizeni[1] = druhy;
	}
	for (size_t i = 0; i < zamestnancu; i ++)
		if (zamestnanci[i].vedouci)
			for (size_t j = 0; j < 2; j ++)
				zamestnanci[zamestnanci[i].podrizeni[j]].nadrizenych ++;
	size_t *skladiste = calloc(zamestnancu, sizeof *skladiste);
	size_t sk_pos = 0;
	for (size_t i = 0; i < zamestnancu; i ++)
		if (zamestnanci[i].nadrizenych == 0)
			skladiste[sk_pos ++] = i;
	while (sk_pos > 0) {
		struct zamestnanec *z = &zamestnanci[skladiste[-- sk_pos]];
		for (size_t i = 0; i < 2; i ++)
			zamestnanci[z->podrizeni[i]].ukolu += (z->ukolu + (i == z->dalsi)) % 2;
		z->dalsi += z->ukolu % 2; // Přesunout v případě lichého
		z->dalsi %= 2; // 2 -> 0
		for (size_t i = 0; i < 2; i ++)
			if (-- zamestnanci[z->podrizeni[i]].nadrizenych == 0)
				skladiste[sk_pos ++] = z->podrizeni[i];
	}
	for (size_t i = 0; i < zamestnancu; i ++)
		if (zamestnanci[i].vedouci)
			printf("%zu %hhu\n", i, zamestnanci[i].dalsi);
	return 0;
}