#include<bits/stdc++.h>
using namespace std;

#define  all(x)        (x).begin(),(x).end()
#define  pb            push_back
#define  lb            lower_bound
#define  ub            upper_bound
#define  fi            first
#define  se            second
#define  pii           pair<int,int>
#define  fastIO        ios_base::sync_with_stdio(false); cin.tie(NULL);
#define  mp            make_pair
#define endl '\n'
#define int long long

typedef double db;
typedef long long ll;

const int N = 1e5 + 5;
const int MOD = 1e9 + 7;
const int INF = 1e12;

int arr[801][801];
int dp[801][801];
int n, k;

bool isPossible(int median) {

	//build prefix sum to calc size of each k*k submatrix in O(1)
	memset(dp, 0, sizeof(dp));

	//1 if element is smaller than or equal to median
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			dp[i][j] = (arr[i][j] <= median) ? 1 : 0;
		}
	}

	//build pref sum
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {

			if (i == 0 && j == 0) continue;
			else if (i == 0) {
				dp[i][j] += dp[i][j - 1];
			}
			else if (j == 0) {
				dp[i][j] += dp[i - 1][j];
			}
			else {
				dp[i][j] += (dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]);
			}
		}
	}

	//check if any subarray has cnt of 1s >= (k*k - 1)/2
	int limit = ((k * k) - 1) / 2;
	for (int i = k - 1; i < n; i++) {
		for (int j = k - 1; j < n; j++) {
			int cnt = dp[i][j];

			if ((i - k) >= 0) cnt -= dp[i - k][j];
			if ((j - k) >= 0) cnt -= dp[i][j - k];
			if ((i - k) >= 0 && (j - k) >= 0) cnt += dp[i - k][j - k];

			if (cnt > limit) return true;
		}
	}
	return false;
}

void solve() {

	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
		}
	}

	int s = 0, e = 1e9 + 5;
	int ans = e;

	while (s <= e) {

		int mid = (s + e) / 2;

		if (isPossible(mid)) {
			ans = mid;
			e = mid - 1;
		}
		else {
			s = mid + 1;
		}
	}

	cout << ans;
}

signed main() {

#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	fastIO

	int t = 1;
	// cin >> t;

	for (int tt = 1; tt <= t; tt++) {
		solve();
	}
}
#include<bits/stdc++.h>
using namespace std;
#define f(i,a,b) for(register int i=a;i<=b;++i)
#define ll long long
#define N 200005
#define se second
#define fi first
#define pb push_back 
#define mp make_pair
inline ll read(){ll x;scanf("%lld",&x);return x;}
vector<ll>eg[N];
ll d[N],edge[N][3],deep[N];
void dfs(int s,int dad)
{
	deep[s]=deep[dad]+1;
	for(auto v:eg[s])if(v!=dad)
	{
		dfs(v,s);
	}
}
void dfs2(int s,int dad)
{
	for(auto v:eg[s])if(v!=dad)
	{
		d[v]+=d[s];
		dfs2(v,s);
	}
}
void solve()
{
	ll n=read();
	f(i,1,n-1)
	{
		edge[i][1]=read();
		edge[i][2]=read();
		eg[edge[i][1]].pb(edge[i][2]);
		eg[edge[i][2]].pb(edge[i][1]);
	}
	dfs(1,0);
	ll q=read();
	f(i,1,q)
	{
		ll op=read(),e=read(),x=read();
		if(op==1)
		{
			if(deep[edge[e][1]]>deep[edge[e][2]]) d[edge[e][1]]+=x;
			else d[1]+=x,d[edge[e][2]]-=x;
		}
		else
		{
			if(deep[edge[e][1]]>deep[edge[e][2]]) d[1]+=x,d[edge[e][1]]-=x;
			else d[edge[e][2]]+=x;
		}
	}
	dfs2(1,0);
	f(i,1,n) printf("%lld\n",d[i]);
}
int main()
{
	ll T=1;
	while(T--) solve();
	return 0;
}